Bricks Falling When Hit · bossfight.dev

grid is a wall: 1 is a brick and 0 is an empty cell. Row 0 is the top row, fixed to the ceiling. A brick is stable if it is in the top row, or if it shares a side (up, down, left or right) with a stable brick. Put another way, a brick is stable exactly when a chain of bricks, each sharing a side with the next, links it to the top row. Every brick is stable at the start.

hits lists cells [r, c] that are hit one after another. A hit removes the brick in that cell. Then every brick that is no longer stable falls at once and disappears from the grid (falling bricks never land on anything or hold anything up). If the cell is already empty when it is hit, because it never had a brick, its brick fell earlier, or it was hit before, the hit does nothing.

Write bricks_fall(grid: list[list[int]], hits: list[list[int]]) -> list[int]: for each hit, how many bricks fell because of it. The brick that was hit doesn't count.

Examples:

grid = [[1, 0, 0, 1],
        [1, 1, 0, 1],
        [0, 1, 1, 1],
        [0, 0, 1, 0]]
bricks_fall(grid, [[1, 1], [0, 3], [3, 2], [0, 1]])  # [0, 5, 0, 0]

Hit 1 removes [1, 1]. The bricks below it still hang from [0, 3] through the right-hand column, so nothing falls: 0.
Hit 2 removes [0, 3]. Now [1, 3], [2, 3], [2, 2], [2, 1] and [3, 2] have no chain to the top row, and all five fall: 5.
Hit 3 lands on [3, 2], whose brick fell at hit 2, and hit 4 on [0, 1], which was always empty: 0 each.

Left: the 4 by 4 wall with the hit cells numbered 1 to 4; the bricks hang from the top row at columns 0 and 3. Right: after hit 1 removed the brick at row 1, column 1, hit 2 removes the brick at row 0, column 3, and the five bricks that hung from it fall

bricks_fall([[1], [1], [1]], [[0, 0], [0, 0]])  # [2, 0]   the second hit finds the cell empty
bricks_fall([[1, 1, 1], [0, 1, 0]], [[0, 1]])   # [1]      the top-row bricks at the sides stay put

Constraints:

1 <= rows, cols <= 200, every cell is 0 or 1, and every brick starts stable.
1 <= len(hits) <= 4 * 10^4, and every hit is inside the grid. The same cell can be hit more than once.

⭐ Bonus: speed tests on 200 × 200 walls with up to 20,000 hits earn a star in close to O(rows · cols + k) time, where k = len(hits). Checking which bricks are still held up after every hit costs up to 40,000 cells per hit there.