1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
| // @Title: 打砖块 (Bricks Falling When Hit)
// @Author: 15816537946@163.com
// @Date: 2021-01-16 22:36:18
// @Runtime: 292 ms
// @Memory: 9.1 MB
var (
rows, cols int
_directions = [][]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}}
)
func hitBricks(grid [][]int, hits [][]int) []int {
rows, cols = len(grid), len(grid[0])
// 第一步， 把 grid 中的砖头全部击碎，通常算法问题不能修改输入数据， 这一步非必需，可以认为是一种答题规范
// 注意：因为 Go Slice 的机制，这里必须进行深拷贝
copied := make([][]int, rows)
for i, v := range grid {
copied[i] = make([]int, len(v))
for j := range v {
copied[i][j] = grid[i][j]
}
}
for _, v := range hits {
copied[v[0]][v[1]] = 0
}
// 第二步，建图，把砖块和砖块的连接关系输入并查集， size 表示二维网格的大小， 也表示虚拟的“屋顶”在并查集中的编号
size := rows * cols
uf := NewUnionFind(size + 1)
// 将下标为 0 的这一行的砖块与“屋顶”相连
for i := 0; i < cols; i++ {
if copied[0][i] == 1 {
uf.union(i, size)
}
}
// 其余网格，如果是砖块向上、向左看一下，如果也是砖块，在并查集中进行合并
for i := 1; i < rows; i++ {
for j := 0; j < cols; j++ {
if copied[i][j] == 1 {
// 如果上方也是砖块
if copied[i-1][j] == 1 {
uf.union(getIndex(i-1, j), getIndex(i, j))
}
// 如果左边也是砖块
if j > 0 && copied[i][j-1] == 1 {
uf.union(getIndex(i, j-1), getIndex(i, j))
}
}
}
}
// 第三步，按照 hits 的逆序， 在 copied 中补回砖块，把每一次因为补回砖块而与屋顶相连的砖块的增量记录到 res 数组中
n := len(hits)
res := make([]int, n)
for i := n - 1; i >= 0; i-- {
x, y := hits[i][0], hits[i][1]
// 注意： 这里不能 copy, 语义上表示，如果原来在 grid 中，这一块是空白的， 这一步补回产生任何砖块掉落
// 逆向补回的时候，与屋顶相连的砖块数量也肯定不会增加
if grid[x][y] == 0 {
continue
}
// 补回之前与屋顶相连的砖块数
origin := uf.getSize(size)
// 注意： 如果补回的这个节点在第一行，要告诉并查集它与屋顶相连（逻辑同第2步）
if x == 0 {
uf.union(y, size)
}
// 在 4 个方向上看一下，如果相邻的4个方向有砖块,合并它们
for _, i := range _directions {
newX, newY := x+i[0], y+i[1]
if inArea(newX, newY) && copied[newX][newY] == 1 {
uf.union(getIndex(x, y), getIndex(newX, newY))
}
}
// 补回之后与屋顶相连的砖块数
current := uf.getSize(size)
// 减去的 1 是逆向补回的砖块（正向移除的砖块），与 0 比较大小，是因为存在一种情况，添加当前砖块，不会使得与屋顶连接的砖块数更多
res[i] = max(0, current-origin-1)
// 真正补上这个砖块
copied[x][y] = 1
}
return res
}
// 二维坐标转一维坐标
func getIndex(x, y int) int {
return x*cols + y
}
// 输入坐标在二维网格中是否越界
func inArea(x, y int) bool {
return x >= 0 && x < rows && y >= 0 && y < cols
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type unionFind struct {
parent []int // 当前节点的父亲节点
size []int // 以当前节点为根子树的节点总数
}
func NewUnionFind(n int) *unionFind {
p := make([]int, n)
s := make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
s[i] = 1
}
return &unionFind{
parent: p,
size: s,
}
}
// 路径压缩，只要求每个不相交集合的“根节点”的子树包含的节点总数数值正确即可，因此在路径压缩的过程中不用维护数组 size
func (u *unionFind) find(x int) int {
if x != u.parent[x] {
u.parent[x] = u.find(u.parent[x])
}
return u.parent[x]
}
func (u *unionFind) union(x, y int) {
rootX, rootY := u.find(x), u.find(y)
if rootX == rootY {
return
}
u.parent[rootX] = rootY
u.size[rootY] += u.size[rootX]
}
// 在并查集的根节点的子树包含的节点总数
func (u *unionFind) getSize(x int) int {
root := u.find(x)
return u.size[root]
}
|