#include <vector> // both n*n
#include <queue>
using namespace std;
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = (int)grid.size();
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        if (n == 1) return 1;
        queue<pair<int, int>> q;
        grid[0][0] = 1;
        q.push({0, 0});
        int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
        int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};
        int dist = 1;
        while (!q.empty()) {
            int sz = (int) q.size();
            while (sz--) {
                auto [x, y] = q.front();
                q.pop();
                if (x == n - 1 && y == n - 1) return dist;
                for (int k = 0 ; k < 8 ; ++k) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        grid[nx][ny] = 1;
                        q.push({nx, ny});
                    }
                }
            }
            dist++;
        }
        return -1;
    }
};