Leetcode 1091. 二进制矩阵中的最短路径 八个方向寻路最短路径 （BFS）

题意抽象就是，从左上角走到右下角，0表示可以通行，1表示不能通行，直接就是裸的BFS题目，这道题目还可以用启发式搜索A*方法来优化，这个算法一般面试中不会出现，仅仅需要口述思想即可。

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if(grid[0][0]==1||grid[n-1][n-1]==1) return -1;
        queue<pair<int,int>> q;
        q.push({0,0});
        grid[0][0] = 2;
        int dis = 0;
        while(!q.empty()){
            int k = q.size();
            while(k--){
                auto pos = q.front();q.pop();
                if(pos.first==n-1&&pos.second==n-1) return dis+1;
                for(int i=-1;i<=1;i++){
                    for(int j=-1;j<=1;j++){
                        if(i==0&&j==0) continue;
                        int x = pos.first + i;
                        int y = pos.second + j;
                        if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==0){
                            q.push({x,y});
                            grid[x][y] = 2;
                        }
                    }
                }
            }
            dis++;
        }
        return -1;
    }
};