<p>You are given an <code>m x n</code> binary <code>grid</code>, where each <code>1</code> represents a brick and <code>0</code> represents an empty space. A brick is <strong>stable</strong> if:</p>

<ul>
	<li>It is directly connected to the top of the grid, or</li>
	<li>At least one other brick in its four adjacent cells is <strong>stable</strong>.</li>
</ul>

<p>You are also given an array <code>hits</code>, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location <code>hits[i] = (row<sub>i</sub>, col<sub>i</sub>)</code>. The brick on that location&nbsp;(if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will <strong>fall</strong>. Once a brick falls, it is <strong>immediately</strong> erased from the <code>grid</code> (i.e., it does not land on other stable bricks).</p>

<p>Return <em>an array </em><code>result</code><em>, where each </em><code>result[i]</code><em> is the number of bricks that will <strong>fall</strong> after the </em><code>i<sup>th</sup></code><em> erasure is applied.</em></p>

<p><strong>Note</strong> that an erasure may refer to a location with no brick, and if it does, no bricks drop.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
<strong>Output:</strong> [2]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [<u>1</u>,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,<u>1</u>,<u>1</u>,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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
<strong>Output:</strong> [0,0]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [1,<u>1</u>,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],
 [<u>1</u>,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].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>grid[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= hits.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>hits[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i&nbsp;</sub>&lt;= m - 1</code></li>
	<li><code>0 &lt;=&nbsp;y<sub>i</sub> &lt;= n - 1</code></li>
	<li>All <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are unique.</li>
</ul>

class UnionFind:
    def __init__(self):
        self.node_to_dad = {}
        self.set_to_size = {}

    def add(self, x) -> None:
        if x in self.node_to_dad: return
        self.node_to_dad[x] = None
        self.set_to_size[x] = 1

    def merge(self, x, y) -> None:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y: return
        self.node_to_dad[root_x] = root_y
        self.set_to_size[root_y] += self.set_to_size[root_x]
        del self.set_to_size[root_x]

    def find(self, x): # return root of x
        root = x
        while self.node_to_dad[root] != None:
            root = self.node_to_dad[root]
        flyer = x
        while flyer != root:
            flyer_dad = self.node_to_dad[flyer]
            self.node_to_dad[flyer] = root
            flyer = flyer_dad
        return root

    def getNumberOfSet(self) -> int:
        return len(self.set_to_size)

    def getSetSize(self, x) -> int:
        return self.set_to_size[self.find(x)]

    def isInGraph(self, x) -> bool:
        return x in self.node_to_dad


class Solution:
    def __init__(self):
        self.WALL = (-1, -1)

    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        # init
        uf = UnionFind()
        rst = [0] * len(hits)
        self.initToAfterHit(grid, hits, uf) # init the uf and grid with the state after all hitting
        # print("grid: ", grid, "uf: ", uf)

        # add bricks
        for idx in range(len(hits) - 1, -1, -1):
            i, j = hits[idx][0], hits[idx][1]
            grid[i][j] += 1
            if grid[i][j] < 1: continue # positions never have brick

            # size of WALL before add
            wall_size_before = uf.getSetSize(self.WALL)
            # add back brick and merge
            uf.add((i, j))
            if i == 0: uf.merge((i, j), self.WALL)
            for nbr in self.getNeighbors(i, j, len(grid), len(grid[0])):
                if grid[nbr[0]][nbr[1]] == 1: uf.merge(nbr, (i, j))
            # size of WALL after add
            wall_size_after = uf.getSetSize(self.WALL)
            rst[idx] = 0 if wall_size_after == wall_size_before else wall_size_after - wall_size_before - 1
        return rst


    def initToAfterHit(self, grid, hits, uf) -> None:
        # hit all bricks
        for i, j in hits:
            grid[i][j] -= 1 # empty hit positions will turn to < 0
        # print(grid)

        # add the remaining bricks to uf
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1: uf.add((i, j))
        uf.add(self.WALL)
        # merge the top line bricks to WALL
        for j in range(len(grid[0])):
            if grid[0][j] == 1: uf.merge((0, j), self.WALL)
        # merge the bricks with its nbrs
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] != 1: continue
                for nbr in self.getNeighbors(i, j, len(grid), len(grid[0])):
                    if grid[nbr[0]][nbr[1]] == 1: uf.merge(nbr, (i, j))


    def getNeighbors(self, i, j, row_num, col_num):
        rst = []
        for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
            if 0 <= x < row_num and 0 <= y < col_num:
                rst.append((x, y))
        return rst



27600