Bricks Falling When Hit LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Helper function to determine if the passed node is connected to the top of
4
  // the matrix
5
  bool isConnected(vector<vector<bool>> &vis, int &i, int &j) {
6
    if (i == 0) return true;
7

8
    if (i > 0 && vis[i - 1][j]) return true;
9
    if (j > 0 && vis[i][j - 1]) return true;
10
    if (i < vis.size() - 1 && vis[i + 1][j]) return true;
11
    if (j < vis[0].size() - 1 && vis[i][j + 1]) return true;
12

13
    return false;
14
  }
15

16
  vector<int> hitBricks(vector<vector<int>> &grid, vector<vector<int>> &hits) {
17
    vector<int> ans(hits.size(), 0);
18

19
    // Remove all the bricks which are hit during entire process
20
    vector<vector<int>> mat = grid;
21
    for (int i = 0; i < hits.size(); i++) mat[hits[i][0]][hits[i][1]] = 0;
22

23
    // Do BFS to determine connected nodes (to top of matrix) and mark them as
24
    // visited
25
    vector<vector<bool>> vis(grid.size(), vector<bool>(grid[0].size(), false));
26
    queue<pair<int, int>> q;
27
    for (int i = 0; i < grid[0].size(); i++) {
28
      if (mat[0][i] == 1) {
29
        vis[0][i] = true;
30
        q.push({0, i});
31
      }
32
    }
33
    while (!q.empty()) {
34
      int idx = q.front().first, jdx = q.front().second;
35
      q.pop();
36

37
      if (idx > 0 && mat[idx - 1][jdx] == 1) {
38
        if (!vis[idx - 1][jdx]) q.push({idx - 1, jdx});
39
        vis[idx - 1][jdx] = true;
40
      }
41
      if (jdx > 0 && mat[idx][jdx - 1] == 1) {
42
        if (!vis[idx][jdx - 1]) q.push({idx, jdx - 1});
43
        vis[idx][jdx - 1] = true;
44
      }
45
      if (idx < grid.size() - 1 && mat[idx + 1][jdx] == 1) {
46
        if (!vis[idx + 1][jdx]) q.push({idx + 1, jdx});
47
        vis[idx + 1][jdx] = true;
48
      }
49
      if (jdx < grid[0].size() - 1 && mat[idx][jdx + 1] == 1) {
50
        if (!vis[idx][jdx + 1]) q.push({idx, jdx + 1});
51
        vis[idx][jdx + 1] = true;
52
      }
53
    }
54

55
    // Traverse the hits array in reverse order to one by one add a brick
56
    for (int i = hits.size() - 1; i >= 0; i--) {
57
      // If no brick was present in original grid matrix, continue, otherwise
58
      // add brick to that position
59
      if (grid[hits[i][0]][hits[i][1]] == 0) continue;
60
      mat[hits[i][0]][hits[i][1]] = 1;
61

62
      // If this brick not connected to top of matrix, ans=0 and continue
63
      if (!isConnected(vis, hits[i][0], hits[i][1])) continue;
64

65
      // This brick connects between visited nodes and not visited nodes, do BFS
66
      // to make all reachable nodes visited and count them
67
      q.push({hits[i][0], hits[i][1]});
68
      vis[hits[i][0]][hits[i][1]] = true;
69
      int cnt = 0;
70
      while (!q.empty()) {
71
        int idx = q.front().first, jdx = q.front().second;
72
        q.pop();
73
        cnt++;
74
        if (idx > 0 && mat[idx - 1][jdx] == 1 && !vis[idx - 1][jdx]) {
75
          q.push({idx - 1, jdx});
76
          vis[idx - 1][jdx] = true;
77
        }
78
        if (jdx > 0 && mat[idx][jdx - 1] == 1 && !vis[idx][jdx - 1]) {
79
          q.push({idx, jdx - 1});
80
          vis[idx][jdx - 1] = true;
81
        }
82
        if (idx < grid.size() - 1 && mat[idx + 1][jdx] == 1 && !vis[idx + 1][jdx]) {
83
          q.push({idx + 1, jdx});
84
          vis[idx + 1][jdx] = true;
85
        }
86
        if (jdx < grid[0].size() - 1 && mat[idx][jdx + 1] == 1 && !vis[idx][jdx + 1]) {
87
          q.push({idx, jdx + 1});
88
          vis[idx][jdx + 1] = true;
89
        }
90
      }
91
      ans[i] = cnt - 1;
92
    }
93
    return ans;
94
  }
95
};