## Algorithm

Problem Name: 803. Bricks Falling When Hit

You are given an `m x n` binary `grid`, where each `1` represents a brick and `0` represents an empty space. A brick is stable if:

• It is directly connected to the top of the grid, or
• At least one other brick in its four adjacent cells is stable.

You are also given an array `hits`, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location `hits[i] = (rowi, coli)`. The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the `grid` (i.e., it does not land on other stable bricks).

Return an array `result`, where each `result[i]` is the number of bricks that will fall after the `ith` erasure is applied.

Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.

Example 1:

```Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: 
Explanation: Starting with the grid:
[[1,0,0,0],
[1,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
[0,1,1,0]]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
[0,0,0,0]]
Hence the result is .
```

Example 2:

```Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: Starting with the grid:
[[1,0,0,0],
[1,1,0,0]]
We erase the underlined brick at (1,1), resulting in the grid:
[[1,0,0,0],
[1,0,0,0]]
All remaining bricks are still stable, so no bricks fall. The grid remains the same:
[[1,0,0,0],
[1,0,0,0]]
Next, we erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
[0,0,0,0]]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is [0,0].
```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 200`
• `grid[i][j]` is `0` or `1`.
• `1 <= hits.length <= 4 * 104`
• `hits[i].length == 2`
• `0 <= xi <= m - 1`
• `0 <= yi <= n - 1`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector hitBricks(vector>& grid, vector>& hits) {
vectorres;
int m = grid.size(), n = grid.size();
for (auto& v: hits) {
int r = v, c = v, count = 0;
grid[r][c] = 0;
if(!reachTop(grid, r - 1, c, m, n)) {
erase(grid, r - 1, c, m, n, count);
}
if(!reachTop(grid, r + 1, c, m, n)) {
erase(grid, r + 1, c, m, n, count);
}
if(!reachTop(grid, r, c - 1, m, n)) {
erase(grid, r, c - 1, m, n, count);
}
if(!reachTop(grid, r, c + 1, m, n)) {
erase(grid, r, c + 1, m, n, count);
}
res.push_back(count);
}
return res;
}

bool reachTop(vector>& grid, int r, int c, int m, int n) {
if (r < 0 || c < 0 || r == m || c == n || grid[r][c] == 0) {
return false;
}
if (r == 0) {
return true;
}
int tmp = grid[r][c];
grid[r][c] = 0;
bool res = reachTop(grid, r + 1, c, m, n) || reachTop(grid, r, c + 1, m, n)
|| reachTop(grid, r - 1, c, m, n) || reachTop(grid, r, c - 1, m, n);
grid[r][c] = tmp;
return res;
}

void erase(vector>& grid, int r, int c, int m, int n, int& count) {
if (r < 0 || c < 0 || r == m || c == n || grid[r][c] == 0) {
return;
}
++count;
grid[r][c] = 0;
erase(grid, r + 1, c, m, n, count);
erase(grid, r - 1, c, m, n, count);
erase(grid, r, c + 1, m, n, count);
erase(grid, r, c - 1, m, n, count);
}
};
``````
Copy The Code &

Input

cmd
grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]

Output

cmd


### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const hitBricks = function (grid, hits) {
const n = grid.length
const m = hits.length
const res = new Array(m).fill(0)
for (const [r, c] of hits) {
if (grid[r][c] == 1) grid[r][c] = 0
else grid[r][c] = -1
}
for (let j = 0; j < n; j++) {
getConnectedCount(grid, 0, j)
}
for (let i = m - 1; i >= 0; i--) {
const [r, c] = hits[i]
if (grid[r][c] == -1) continue
grid[r][c] = 1
if (isConnectedToTop(grid, r, c)) {
res[i] = getConnectedCount(grid, r, c) - 1
}
}
return res
}
const isConnectedToTop = (grid, i, j) => {
if (i == 0) return true
const dircs = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
]
for (const [dx, dy] of dircs) {
const nx = i + dx
const ny = j + dy
if (
0 <= nx &&
nx < grid.length &&
0 <= ny &&
ny < grid.length &&
grid[nx][ny] == 2
) {
return true
}
}
return false
}

const getConnectedCount = (grid, i, j) => {
if (
i < 0 ||
i >= grid.length ||
j < 0 ||
j >= grid.length ||
grid[i][j] != 1
)
return 0
let count = 1
grid[i][j] = 2
count +=
getConnectedCount(grid, i + 1, j) +
getConnectedCount(grid, i - 1, j) +
getConnectedCount(grid, i, j + 1) +
getConnectedCount(grid, i, j - 1)
return count
}
``````
Copy The Code &

Input

cmd
grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]

Output

cmd


### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def hitBricks(self, grid, hits):
m, n, ret = len(grid), len(grid), *len(hits)
# Connect unconnected bricks and
def dfs(i, j):
if not (0 <= i ``````
``` Copy The Code & Input x – + cmd grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]] Output x – + cmd [0,0] ```
``` Demonstration ```
``` #802 Leetcode Find Eventual Safe States Solution in C, C++, Java, JavaScript, Python, C# Leetcode #804 Leetcode Unique Morse Code Words Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```