1091

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), steps = 1;
        bool vis[n][m];
        memset(vis, 0, sizeof vis);
        if(n-1 == 0 && m-1 == 0) return 1;
        if(grid[0][0]) return -1;
        queue<pair<int, int>> q;
        q.push({0,0});
        vis[0][0] = true;

        int dir[8][2] = {{-1,0},{-1,-1},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                for(int k=0; k<8; k++){
                    int nextX = p.first+dir[k][0], nextY=p.second+dir[k][1];
                    if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || vis[nextX][nextY] || grid[nextX][nextY]) continue;
                    vis[nextX][nextY] = true;
                    if(nextX == n-1 && nextY == m-1){
                        return steps+1;
                    }
                    q.push({nextX, nextY});
                }
            }
            steps++;
        }
        return -1;
    }
};