-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
803. Bricks Falling When Hit.go
66 lines (61 loc) · 1.39 KB
/
803. Bricks Falling When Hit.go
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
package leetcode
import (
"github.com/halfrost/LeetCode-Go/template"
)
var dir = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
func hitBricks(grid [][]int, hits [][]int) []int {
if len(hits) == 0 {
return []int{}
}
uf, m, n, res, oriCount := template.UnionFindCount{}, len(grid), len(grid[0]), make([]int, len(hits)), 0
uf.Init(m*n + 1)
// 先将要打掉的砖块染色
for _, hit := range hits {
if grid[hit[0]][hit[1]] == 1 {
grid[hit[0]][hit[1]] = 2
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
getUnionFindFromGrid(grid, i, j, uf)
}
}
}
oriCount = uf.Count()[uf.Find(m*n)]
for i := len(hits) - 1; i >= 0; i-- {
if grid[hits[i][0]][hits[i][1]] == 2 {
grid[hits[i][0]][hits[i][1]] = 1
getUnionFindFromGrid(grid, hits[i][0], hits[i][1], uf)
}
nowCount := uf.Count()[uf.Find(m*n)]
if nowCount-oriCount > 0 {
res[i] = nowCount - oriCount - 1
} else {
res[i] = 0
}
oriCount = nowCount
}
return res
}
func isInGrid(grid [][]int, x, y int) bool {
return x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0])
}
func getUnionFindFromGrid(grid [][]int, x, y int, uf template.UnionFindCount) {
m, n := len(grid), len(grid[0])
if x == 0 {
uf.Union(m*n, x*n+y)
}
for i := 0; i < 4; i++ {
nx := x + dir[i][0]
ny := y + dir[i][1]
if isInGrid(grid, nx, ny) && grid[nx][ny] == 1 {
uf.Union(nx*n+ny, x*n+y)
}
}
}