力扣1210. 穿过迷宫的最少移动次数

力扣1210. 穿过迷宫的最少移动次数

题目

题目解析及思路

题目要求找到最短的贪吃蛇到出口的路径，并且必须横着出去

就是比一般bfs多了一维，贪吃蛇当前水平还是竖直

代码

class Solution {
    static constexpr int dir[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<tuple<int,int,int>> q;
        q.emplace(0,0,0);
        vector<vector<vector<int>>> dis(n, vector<vector<int>>(n, vector<int>(2, INT_MAX)));
        dis[0][0][0] = 0;

        auto bfs = [&]()->void{
            while(!q.empty()){
                auto [x,y,s] = q.front();
                q.pop();
                for(int i=0;i<3;i++){
                    int sx = x + dir[i][0];
                    int sy = y + dir[i][1];
                    //更新状态
                    int ss = s ^ dir[i][2];
                    //求头的坐标
                    int hx = sx + ss;
                    int hy = sy + (ss ^ 1);
                    //头的位置是1、尾的位置是1、尾右下的位置是1，都不行
                    if(hx >= n || hy >= n || sx >= n || sy >= n || ss >= 2 || grid[hx][hy] == 1 || grid[sx][sy] == 1 || (i == 2 && grid[x+1][y+1] == 1)){
                        continue;
                    }
                    if(dis[sx][sy][ss] > dis[x][y][s] + 1){
                        dis[sx][sy][ss] = dis[x][y][s] + 1;
                        q.emplace(sx,sy,ss);
                    }
                }
            }
        };

        bfs();
        return dis[n-1][n-2][0] >= INT_MAX/2 ? -1 : dis[n-1][n-2][0];
    }
};