aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_binary_matrix.cpp
blob: 67cd095c35165a7a199b695da3778eb19422f0a0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "leetcode.h"
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

class Solution {
public:
  int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
    if (grid[0][0] || grid.back().back())
      return -1;
    int ans = 2, len = 1, nX = grid[0].size() - 1, nY = grid.size() - 1;
    queue<pair<int, int>> qp;
    if (!nX && !nY)
      return 1 - (grid[0][0] << 1);
    qp.push({0, 0});
    grid[0][0] = -1;
    while (len) {
      while (len--) {
        auto [cX, cY] = qp.front();
        qp.pop();
        for (int i = max(0, cX - 1), lmtX = min(cX + 1, nX); i <= lmtX; i++) {
          for (int j = max(0, cY - 1), lmtY = min(cY + 1, nY); j <= lmtY; j++) {
            if (i == nX && j == nY)
              return ans;
            if (!grid[j][i]) {
              grid[j][i] = -1;
              qp.push({i, j});
            }
          }
        }
      }
      ans++;
      len = qp.size();
    }
    return -1;
  }
};

int main() {}