A grid of 1 (brick) and 0 (empty). A brick is stable if it is in the top row or is adjacent (up, down, left, right) to a stable brick. The starting grid is stable. You are given hits, a list of [row, col] cells erased one after another: a hit removes the brick there if there is one, and then every brick that is no longer stable falls and disappears. Return an array where result[i] is the number of bricks that fall because of hit i (not counting the brick that was hit).
- A
DSU class with find(x), union(a, b) (returns false when they were already together), setSize(x) and a components counter is already provided - A hit on an empty cell, or on a cell already cleared, drops nothing:
0 - Union-find cannot split a set, so think of the hits in reverse order
- Do not modify the input grid