class Solution {
public:


    bool validPosition(int x, int y, int n, int m, vector<vector<int>>& grid){
        if(x < 0 or x >= n or y < 0 or y >= m) return false;
        return grid[x][y] == 0;
    }

    struct coord{
        int x, y;
        coord(int _x, int _y){
            x = _x;
            y = _y;
        }
    };


    int shortestPathBinaryMatrixUtil(vector<vector<int>>& grid){

        if(grid.empty() or grid[0][0] == 1) return -1;

        int n = grid.size();
        int m = grid[0].size();

        vector<vector<int>> dist(n, vector<int>(m, INT_MAX - 1));
        dist[0][0] = 0;

        queue<coord> bfsQ;
        bfsQ.push(coord(0,0));


        while(bfsQ.empty() == false){
            coord currPoint = bfsQ.front();
            bfsQ.pop();
            for(int dx = -1; dx <= 1; dx++){
                for(int dy = -1; dy <= 1; dy++){
                    if(dx == 0 and dy == 0) continue;
                    int newX = currPoint.x + dx;
                    int newY = currPoint.y + dy;
                    if(validPosition(newX, newY, n, m, grid)){
                        if(dist[currPoint.x][currPoint.y] + 1 < dist[newX][newY]){
                            dist[newX][newY] = dist[currPoint.x][currPoint.y] + 1;
                            bfsQ.push(coord(newX, newY));
                        }
                    }
                }
            }
        }

        return dist[n - 1][m - 1] == (INT_MAX - 1) ? -1: dist[n - 1][m - 1] + 1;
    }


    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int shortestPath = shortestPathBinaryMatrixUtil(grid);
        return shortestPath;
    }
};