力扣1091. 二进制矩阵中的最短路径

力扣1091. 二进制矩阵中的最短路径

题目

题目解析及思路

题目要求找到一条左上到右下的最短路径

八方向bfs板子

代码

class Solution {
    int dx[8] = {0,1,0,-1,1,1,-1,-1},dy[8] = {1,0,-1,0,-1,1,-1,1};
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if(grid[0][0] == 1) return -1;
        queue<pair<int,int>> q;
        vector<vector<int>> dis(n,vector<int>(n,INT_MAX));

        auto bfs = [&]()->void{
            while(!q.empty()){
                auto [x,y] = q.front();
                q.pop();
                for(int i=0;i<8;i++){
                    int sx = x + dx[i];
                    int sy = y + dy[i];
                    if(sx < 0 || sx >= n || sy < 0 || sy >= n || grid[sx][sy] == 1){
                        continue;
                    }
                    if(dis[sx][sy] > dis[x][y] + 1){
                        dis[sx][sy] = dis[x][y] + 1;
                        q.emplace(sx,sy);
                    }
                }
            }
        };

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