有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
- 一块砖直接连接到网格的顶部，或者
- 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 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)互不相同
逆向并查集，考虑补上被击碎的砖块以后，有多少个砖块因为这个补上的这个砖块而与屋顶的砖块相连。每一次击碎一个砖块，因击碎砖块而消失的砖块只会越来越少。因此可以按照数组 hits 的顺序逆序地把这些砖块依次补上。
在实现上，设置一个特殊的节点 m*n，表示屋顶；逆序补回时，增加的连接到屋顶的砖块为 ans[i] = max(0, curr - prev - 1)。因为有可能补回后，连接到屋顶的砖块数量没有发生变化。
此过程中用 size 数组维护每个连通分量的大小。
以下是并查集的几个常用模板。
模板 1——朴素并查集：
# 初始化，p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)模板 2——维护 size 的并查集：
# 初始化，p存储每个点的父节点，size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)模板 3——维护到祖宗节点距离的并查集：
# 初始化，p存储每个点的父节点，d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distanceclass Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
size[pb] += size[pa]
p[pa] = pb
m, n = len(grid), len(grid[0])
p = list(range(m * n + 1))
size = [1] * len(p)
g = deepcopy(grid)
for i, j in hits:
g[i][j] = 0
for j in range(n):
if g[0][j] == 1:
union(j, m * n)
for i in range(1, m):
for j in range(n):
if g[i][j] == 0:
continue
if g[i - 1][j] == 1:
union(i * n + j, (i - 1) * n + j)
if j > 0 and g[i][j - 1] == 1:
union(i * n + j, i * n + j - 1)
ans = []
for i, j in hits[::-1]:
if grid[i][j] == 0:
ans.append(0)
continue
g[i][j] = 1
prev = size[find(m * n)]
if i == 0:
union(j, m * n)
for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and g[x][y] == 1:
union(i * n + j, x * n + y)
curr = size[find(m * n)]
ans.append(max(0, curr - prev - 1))
return ans[::-1]class Solution {
private int[] p;
private int[] size;
public int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length;
int n = grid[0].length;
p = new int[m * n + 1];
size = new int[m * n + 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
size[i] = 1;
}
int[][] g = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = grid[i][j];
}
}
for (int[] h : hits) {
g[h[0]][h[1]] = 0;
}
for (int j = 0; j < n; ++j) {
if (g[0][j] == 1) {
union(j, m * n);
}
}
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 0) {
continue;
}
if (g[i - 1][j] == 1) {
union(i * n + j, (i - 1) * n + j);
}
if (j > 0 && g[i][j - 1] == 1) {
union(i * n + j, i * n + j - 1);
}
}
}
int[] ans = new int[hits.length];
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = hits.length - 1; k >= 0; --k) {
int i = hits[k][0];
int j = hits[k][1];
if (grid[i][j] == 0) {
continue;
}
g[i][j] = 1;
int prev = size[find(m * n)];
if (i == 0) {
union(j, m * n);
}
for (int l = 0; l < 4; ++l) {
int x = i + dirs[l];
int y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {
union(i * n + j, x * n + y);
}
}
int curr = size[find(m * n)];
ans[k] = Math.max(0, curr - prev - 1);
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private void union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa != pb) {
size[pb] += size[pa];
p[pa] = pb;
}
}
}class Solution {
public:
vector<int> p;
vector<int> size;
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int m = grid.size(), n = grid[0].size();
p.resize(m * n + 1);
size.resize(m * n + 1);
for (int i = 0; i < p.size(); ++i)
{
p[i] = i;
size[i] = 1;
}
vector<vector<int>> g(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
g[i][j] = grid[i][j];
for (auto& h : hits) g[h[0]][h[1]] = 0;
for (int j = 0; j < n; ++j)
if (g[0][j] == 1)
merge(j, m * n);
for (int i = 1; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (g[i][j] == 0) continue;
if (g[i - 1][j] == 1) merge(i * n + j, (i - 1) * n + j);
if (j > 0 && g[i][j - 1] == 1) merge(i * n + j, i * n + j - 1);
}
}
vector<int> ans(hits.size());
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = hits.size() - 1; k >= 0; --k)
{
int i = hits[k][0], j = hits[k][1];
if (grid[i][j] == 0) continue;
g[i][j] = 1;
int prev = size[find(m * n)];
if (i == 0) merge(j, m * n);
for (int l = 0; l < 4; ++l)
{
int x = i + dirs[l], y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1)
merge(i * n + j, x * n + y);
}
int curr = size[find(m * n)];
ans[k] = max(0, curr - prev - 1);
}
return ans;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb)
{
size[pb] += size[pa];
p[pa] = pb;
}
}
};func hitBricks(grid [][]int, hits [][]int) []int {
m, n := len(grid), len(grid[0])
p := make([]int, m*n+1)
size := make([]int, len(p))
for i := range p {
p[i] = i
size[i] = 1
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
pa, pb := find(a), find(b)
if pa != pb {
size[pb] += size[pa]
p[pa] = pb
}
}
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = grid[i][j]
}
}
for _, h := range hits {
g[h[0]][h[1]] = 0
}
for j, v := range g[0] {
if v == 1 {
union(j, m*n)
}
}
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if g[i][j] == 0 {
continue
}
if g[i-1][j] == 1 {
union(i*n+j, (i-1)*n+j)
}
if j > 0 && g[i][j-1] == 1 {
union(i*n+j, i*n+j-1)
}
}
}
ans := make([]int, len(hits))
dirs := []int{-1, 0, 1, 0, -1}
for k := len(hits) - 1; k >= 0; k-- {
i, j := hits[k][0], hits[k][1]
if grid[i][j] == 0 {
continue
}
g[i][j] = 1
prev := size[find(m*n)]
if i == 0 {
union(j, m*n)
}
for l := 0; l < 4; l++ {
x, y := i+dirs[l], j+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 {
union(i*n+j, x*n+y)
}
}
curr := size[find(m*n)]
ans[k] = max(0, curr-prev-1)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}