Formatted question description: https://leetcode.ca/all/803.html

# 803. Bricks Falling When Hit

## Level

Hard

## Description

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

**Example 1:**

**Input:**

grid = [[1,0,0,0],[1,1,1,0]]

hits = [[1,0]]

**Output:** [2]

**Explanation:**

If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

**Example 2:**

**Input:**

grid = [[1,0,0,0],[1,1,0,0]]

hits = [[1,1],[1,0]]

**Output:** [0,0]

**Explanation:**

When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.

**Note:**

- The number of rows and columns in the grid will be in the range [1, 200].
- The number of erasures will not exceed the area of the grid.
- It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
- An erasure may refer to a location with no brick - if it does, no bricks drop.

## Solution

First mark the bricks with different numbers. If a brick is erased, mark it with -1. If a brick never drops, mark it with 2.

Then loop over `hits`

backwards. For each `hit`

in `hits`

, do breadth first search. If the current `hit`

is not at the top and no adjacent cell is 2, then the current falling bricks is 0. Otherwise, for all adjacent cells, if the value is 1, increase the falling count by 1 and change the value to 2. After all reachable cells are visited, the current hit’s number of falling bricks can be counted. Finally, return an array that contains each hit’s number of falling bricks.

```
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
int rows = grid.length, columns = grid[0].length;
int[][] tempGrid = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++)
tempGrid[i][j] = grid[i][j];
}
for (int[] hit : hits) {
int row = hit[0], column = hit[1];
if (tempGrid[row][column] == 1)
tempGrid[row][column] = -1;
}
for (int i = 0; i < columns; i++)
breadthFirstSearchTop(tempGrid, 0, i);
int hitsCount = hits.length;
int[] falls = new int[hitsCount];
for (int i = hitsCount - 1; i >= 0; i--) {
int[] hit = hits[i];
falls[i] = breadthFirstSearch(tempGrid, hit[0], hit[1]);
}
return falls;
}
public void breadthFirstSearchTop(int[][] grid, int row, int column) {
if (grid[row][column] == 1) {
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int rows = grid.length, columns = grid[0].length;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{row, column});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int curRow = cell[0], curColumn = cell[1];
grid[curRow][curColumn] = 2;
for (int[] direction : directions) {
int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == 1)
queue.offer(new int[]{newRow, newColumn});
}
}
}
}
public int breadthFirstSearch(int[][] grid, int row, int column) {
if (grid[row][column] == 0)
return 0;
boolean flag = false;
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int rows = grid.length, columns = grid[0].length;
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == 2) {
flag = true;
break;
}
}
if (!flag && row > 0) {
grid[row][column] = 1;
return 0;
}
int fall = 0;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{row, column});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int curRow = cell[0], curColumn = cell[1];
if (grid[curRow][curColumn] == 1)
fall++;
grid[curRow][curColumn] = 2;
for (int[] direction : directions) {
int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == 1)
queue.offer(new int[]{newRow, newColumn});
}
}
return fall;
}
}
```