#803

Bricks Falling When Hit

master · 1800 · lc hard +32 · verified · 37% accepted · 1,202 likes · top 15%

Description

You are given an m x n binary grid where 1 represents a brick and 0 represents empty space. A brick is considered stable when:

- It is directly attached to the top edge of the grid, or

- At least one adjacent brick (in four directions) is itself stable.

You are also given an array hits specifying a sequence of bricks to erase. Erasing the brick at hits[i] = (rowi, coli) removes it (if present), and any bricks that then lose stability will also fall and be erased immediately.

Return an array result where result[i] is the number of bricks that fall after the i^th erasure.

Note: if a hit location contains no brick, no bricks fall.

Example 1:

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]

Output: [2]

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 [2].

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].

Code

1

2

3

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]: