title
有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
- 一块砖直接连接到网格的顶部，或者
- 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。
示例 2：
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0],
[1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j]为0或11 <= hits.length <= 4 * 104hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1- 所有
(xi, yi)互不相同
solution
逆向思维+并查集。
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
uf = {}
count = {}
if not grid:
return []
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
add(a)
add(b)
ra, rb = find(a), find(b)
if ra != rb:
uf[rb] = ra
count[ra] += count[rb]
del count[rb]
return
def add(x):
uf.setdefault(x, x)
count.setdefault(x, 1)
def is_connected(a, b):
ra, rb = find(a), find(b)
return ra == rb
m, n = len(grid), len(grid[0])
res = [0] * len(hits)
for i in range(len(hits)):
x, y = hits[i]
grid[x][y] -= 1
zero = (-1, -1)
add(zero)
dirs = (-1, 0, 1, 0, -1)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
#
if i == 0:
union((i, j), zero)
for k in range(4):
nx, ny = i + dirs[k], j + dirs[k + 1]
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
union((i, j), (nx, ny))
for i in range(len(hits) - 1, -1, -1):
x, y = hits[i]
old = count[find(zero)]
grid[x][y] += 1
if grid[x][y] != 1:
continue
add((x, y))
if x == 0:
union((x, y), zero)
for k in range(4):
nx, ny = x + dirs[k], y + dirs[k + 1]
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
union((x, y), (nx, ny))
if is_connected(zero, (x,y)):
new = count[find(zero)]
res[i] = new - old - 1
return res