1.题目基本信息
1.1.题目描述
有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
-
一块砖直接连接到网格的顶部，或者
-
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
1.2.题目地址
https://leetcode.cn/problems/bricks-falling-when-hit/description/
2.解题方法
2.1.解题思路
并查集+逆序遍历
2.2.解题步骤
第一步，将grid中的hits的节点进行删除，即标记为0
第二步，构建此时grid对应的并查集uf；构建X=-1的虚拟节点，连接顶部所有的节点
第三步，构建维护变量。size维护与X节点连通的节点数量；result维护逆序遍历hits时对应的size的差值，即为结果变量
第四步，逆序遍历hits，将结点依次添加到并查集uf中，并计算添加后的size，更新result
-
4.1.如果当前需要添加的节点在copiedGrid中的值为0，则排除
-
4.2.将当前节点添加并查集中
-
4.3.如果当前节点在顶部，则与X=-1节点连接到同一个连通分量中
-
4.4.将node四周结点与node节点进行连接
-
4.5.查询当前与X=-1节点相连的节点数，并更新result和size维护变量
第五步，返回result
3.解题代码
python代码
class UnionFind():
def __init__(self):
self.roots = {}
self.setCnt = 0
self.rootSizes = {}
def add(self, x):
if x not in self.roots:
self.roots[x] = x
self.rootSizes[x] = 1
self.setCnt += 1
def find(self, x):
root = x
while self.roots[root] != root:
root = self.roots[root]
while x != root:
temp = self.roots[x]
self.roots[x] = root
x = temp
return root
def union(self, x, y):
rootx, rooty = self.find(x), self.find(y)
if rootx != rooty:
if self.rootSizes[rootx] < self.rootSizes[rooty]:
self.roots[rootx] = rooty
self.rootSizes[rooty] += self.rootSizes[rootx]
else:
self.roots[rooty] = rootx
self.rootSizes[rootx] += self.rootSizes[rooty]
# 获取x所在连通分量的大小
def getSize(self, x):
root = self.find(x)
return self.rootSizes[root]
from copy import deepcopy
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
# 思路：并查集
m, n = len(grid), len(grid[0])
copiedGrid = deepcopy(grid)
# 第一步，将grid中的hits的节点进行删除，即标记为0
for r, c in hits:
grid[r][c] = 0
# 第二步，构建此时grid对应的并查集uf；构建X=-1的虚拟节点，连接顶部所有的节点
uf = UnionFind()
uf.add(-1)
for r in range(m):
for c in range(n):
if grid[r][c] != 0:
node = r * n + c
uf.add(node)
if r == 0:
uf.union(node, -1)
if r + 1 < m and grid[r + 1][c] != 0:
node1 = (r + 1) * n + c
uf.add(node1)
uf.union(node, node1)
if c + 1 < n and grid[r][c + 1] != 0:
node2 = r * n + c + 1
uf.add(node2)
uf.union(node, node2)
# print(uf.roots)
# 第三步，构建维护变量。size维护与X节点连通的节点数量；result维护逆序遍历hits时对应的size的差值，即为结果变量
size = uf.getSize(-1) - 1
n2 = len(hits)
result = [0] * n2
# 第四步，逆序遍历hits，将结点依次添加到并查集uf中，并计算添加后的size，更新result
for index, (r, c) in enumerate(hits[::-1]):
# 4.1.如果当前需要添加的节点在copiedGrid中的值为0，则排除
if copiedGrid[r][c] == 0:
continue
# 4.2.将当前节点添加并查集中
node = r * n + c
uf.add(node)
grid[r][c] = 1
# 4.3.如果当前节点在顶部，则与X=-1节点连接到同一个连通分量中
if r == 0:
uf.union(node, -1)
# 4.4.将node四周结点与node节点进行连接
for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
nnode = nr * n + nc
uf.add(nnode)
uf.union(node, nnode)
# 4.5.查询当前与X=-1节点相连的节点数，并更新result和size维护变量
size1 = uf.getSize(-1) - 1
# print("size1", size1, grid, uf.roots)
result[n2 - index - 1] = max(size1 - size - 1, 0)
size = size1
# 第五步，返回result
return result4.执行结果
