1
class Solution {
2
 public:
3
  int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
4
    int m = grid.size(), n = grid[0].size();
5
    if (grid[0][0] != 0 || grid[m - 1][n - 1] != 0) return -1;
6
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
7
    int ans = INT_MAX;
8
    queue<pair<int, int>> q;
9
    dist[0][0] = 1;
10
    q.push({0, 0});
11

12
    int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
13
    while (!q.empty()) {
14
      auto curr = q.front();
15
      q.pop();
16
      for (int i = 0; i < 8; i++) {
17
        int newi = curr.first + dir[i][0];
18
        int newj = curr.second + dir[i][1];
19
        if (newi >= 0 && newi < m && newj >= 0 && newj < n && grid[newi][newj] == 0) {
20
          if (dist[newi][newj] > dist[curr.first][curr.second] + 1) {
21
            dist[newi][newj] = dist[curr.first][curr.second] + 1;
22
            q.push({newi, newj});
23
          }
24
        }
25
      }
26
    }
27

28
    return dist[m - 1][n - 1] == INT_MAX ? -1 : dist[m - 1][n - 1];
29
  }
30
};