Last Day Where You Can Still Cross LeetCode solution in C++

1
class Solution {
2
 public:
3
  int X[4] = {0, 0, -1, 1};
4
  int Y[4] = {-1, 1, 0, 0};
5
  int latestDayToCross(int row, int col, vector<vector<int>> &cells) {
6
    int n = row;
7
    int m = col;
8
    vector<vector<int>> a(n, vector<int>(m, 0));
9
    int x = 0;
10
    for (auto xt : cells) {
11
      int rr = xt[0];
12
      int cc = xt[1];
13
      rr--;
14
      cc--;
15
      if (!bfs(a, n, m)) break;
16
      a[rr][cc] = 1;
17
      x++;
18
    }
19
    if (x == 0) return x;
20
    return x - 1;
21
  }
22
  bool bfs(vector<vector<int>> a, int n, int m) {
23
    queue<pair<int, int>> q;
24
    for (int i = 0; i < m; i++) {
25
      if (a[0][i] == 0) {
26
        q.push({0, i});
27
        a[0][i] = 1;
28
      }
29
    }
30

31
    while (!q.empty()) {
32
      int ss = q.size();
33
      while (ss--) {
34
        pair<int, int> pr = q.front();
35
        q.pop();
36
        int ii = pr.first;
37
        int jj = pr.second;
38
        if (ii == n - 1) return 1;
39
        for (int i = 0; i < 4; i++) {
40
          int nx = ii + X[i];
41
          int ny = jj + Y[i];
42
          if (nx >= 0 and nx < n and ny >= 0 and ny < m and a[nx][ny] == 0) {
43
            q.push({nx, ny});
44
            a[nx][ny] = 1;
45
          }
46
        }
47
      }
48
    }
49
    return 0;
50
  }
51
};