class Solution {
    using Index = pair<int, int>;
    vector<Index> directions =
    {
        {-1, -1},
        {-1, 0},
        {-1, 1},
        {0, -1},
        {0, 1},
        {1, -1},
        {1, 0},
        {1, 1}
    };

public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid)
    {
        const int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
            return -1;

        if (n == 1)
            return 1;
        
        int distance = 1;
        Index target = {n - 1, n - 1};
        queue<Index> q;
        q.push({0, 0});
        grid[0][0] = 1;
        while (!q.empty())
        {
            const int levelSize = q.size();
            for (int i = 0; i < levelSize; i++)
            {
                Index curr = q.front();
                q.pop();
                for (const Index& diff : directions)
                {
                    Index next = {curr.first + diff.first, curr.second + diff.second};
                    if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < n 
                        && grid[next.first][next.second] == 0)
                    {
                        if (next == target)
                            return distance + 1;
                        grid[next.first][next.second] = 1;
                        q.push(next);
                    }
                }
            }
            distance++;
        }
        return -1;
    }
};