1018. Bricks That Fall When a Cell Is Knocked Out

A wall is a grid of r rows and c columns. A cell holds 1 for a brick and 0 for a gap. A brick is STABLE when it is in the top row, or when it shares a side with another stable brick. Every brick in the wall as given is stable.

Then k cells are knocked out, one at a time, in the order listed, and no cell is knocked twice. Knocking out a cell removes whatever is there. After each knock, every brick that is no longer stable falls and is gone from the wall for good.

After each knock, print how many bricks FALL, not counting the knocked cell itself.

``` 111 knock (1,2) -> 1 the brick below loses its only support 010

111 knock (1,2) then (1,1) -> 0 1 100

1 1 knock (1,1) -> 2 1 ```

111 knock (2,1) then (2,3) -> 0 3 101 111

The last wall is a ring. Breaking one side changes nothing because the other side still holds the bottom row up. Breaking the second side drops all three bottom bricks at once.

## Why a disjoint set cannot follow this forwards

Knocking a cell out is a REMOVAL, and the structure has no operation that takes a merge back. Worse, the thing being asked for is the size of the piece that becomes disconnected, which is precisely the information a merge throws away.

## What most people try first

After each knock, traverse the wall from the top row and count the bricks the traversal does not reach. That is O(r c) per knock, so O(k r c) overall, about 4 * 10^8 at the limits with a heavy constant, and it is the version that times out.

## Run the knocks backwards, and anchor the ceiling

Two ideas together.

First, add one EXTRA element to the structure standing for the ceiling, and join every brick in the top row to it. Then "this brick is stable" becomes "this brick is in the ceiling's group", and the number of stable bricks is the size of that group minus one for the ceiling element itself.

Second, do the knocks in reverse. Start from the wall with EVERY knocked cell already removed, build the structure once, then put the cells back from the last knock to the first.

remove all k cells from a copy of the wall build the structure over what is left, joining the top row to the ceiling for t from k-1 down to 0: if the original wall had no brick at cell t: answer 0 and continue before = size of the ceiling group put the brick back and join it to the ceiling if it is in the top row join it to each of its four neighbours that is a brick after = size of the ceiling group answer[t] = max(0, after - before - 1)

## Why the count is after - before - 1

Putting the brick back adds itself and everything that was hanging off it to the stable set. Reading it forwards: knocking that brick out removes exactly those bricks from the stable set, which is after - before bricks, and one of them is the knocked brick itself, which the answer does not count.

The max with 0 is there for the brick that was not stable even after being put back. Then after equals before, the subtraction gives -1, and the right answer is 0: knocking out a brick that is not holding anything up drops nothing.

## The knock that lands on a gap

The order is fixed, so a knock on a cell the wall never had a brick in answers 0 and must not put anything back in the reverse sweep. Check the ORIGINAL wall, not the working copy, because the working copy has had every knocked cell cleared.

## Why the reverse sweep sees the same wall

Working backwards, before step t the structure holds exactly the bricks that survive knocks 0 .. t, which is the wall after knock t. Putting brick t back turns that into the wall after knock t - 1. Since the bricks that fell during a forward knock are exactly the ones that were only stable through the knocked brick, and they are never put back before it, the two walls match at every step.

## Overflow

r c reaches 4 * 10^4, so every count fits easily inside a signed 32 bit integer whose maximum is 2147483647.

## Cross-reference

Problem 1013 uses the same reversal to turn cuts into merges and is the simplest form of it. Problem 793 loses grid cells over time as well and answers with a binary search instead, because the question there is a single yes-or-no threshold rather than a size per step.

## Cost

Time O(r c alpha(r c) + k alpha(r c)). Space O(r c).

Constraints - `1 ≤ r ≤ 200` - `1 ≤ c ≤ 200` - `1 ≤ k ≤ 40000` - `1 ≤ x ≤ r`, `1 ≤ y ≤ c` - No cell is knocked out twice. - Every brick in the given wall is stable.