打砖块。有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：1.一块砖直接连接到网格的顶部，或者，2.至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时。给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
并查集。逆向思维。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
grid := [][]int{{1, 0, 0, 0}, {1, 1, 1, 0}}
hits := [][]int{{1, 0}}
ret := hitBricks(grid, hits)
fmt.Println(ret)
}
func hitBricks(grid [][]int, hits [][]int) []int {
for i := 0; i < len(hits); i++ {
if grid[hits[i][0]][hits[i][1]] == 1 {
grid[hits[i][0]][hits[i][1]] = 2
}
}
unionFind := NewUnionFind(grid)
ans := make([]int, len(hits))
for i := len(hits) - 1; i >= 0; i-- {
if grid[hits[i][0]][hits[i][1]] == 2 {
ans[i] = unionFind.finger(hits[i][0], hits[i][1])
}
}
return ans
}
// 并查集
type UnionFind struct {
N int
M int
// 有多少块砖，连到了天花板上
cellingAll int
// 原始矩阵，因为炮弹的影响，1 -> 2
grid [][]int
// cellingSet[i] = true; i 是头节点，所在的集合是天花板集合
cellingSet []bool
fatherMap []int
sizeMap []int
stack []int
}
func NewUnionFind(matrix [][]int) *UnionFind {
res := &UnionFind{}
res.initSpace(matrix)
res.initConnect()
return res
}
func (this *UnionFind) initSpace(matrix [][]int) {
this.grid = matrix
this.N = len(this.grid)
this.M = len(this.grid[0])
all := this.N * this.M
this.cellingAll = 0
this.cellingSet = make([]bool, all)
this.fatherMap = make([]int, all)
this.sizeMap = make([]int, all)
this.stack = make([]int, all)
for row := 0; row < this.N; row++ {
for col := 0; col < this.M; col++ {
if this.grid[row][col] == 1 {
index := row*this.M + col
this.fatherMap[index] = index
this.sizeMap[index] = 1
if row == 0 {
this.cellingSet[index] = true
this.cellingAll++
}
}
}
}
}
func (this *UnionFind) initConnect() {
for row := 0; row < this.N; row++ {
for col := 0; col < this.M; col++ {
this.union(row, col, row-1, col)
this.union(row, col, row+1, col)
this.union(row, col, row, col-1)
this.union(row, col, row, col+1)
}
}
}
func (this *UnionFind) find(row int, col int) int {
stackSize := 0
index := row*this.M + col
for index != this.fatherMap[index] {
this.stack[stackSize] = index
stackSize++
index = this.fatherMap[index]
}
for stackSize != 0 {
stackSize--
this.fatherMap[this.stack[stackSize]] = index
}
return index
}
func (this *UnionFind) union(r1 int, c1 int, r2 int, c2 int) {
if this.valid(r1, c1) && this.valid(r2, c2) {
father1 := this.find(r1, c1)
father2 := this.find(r2, c2)
if father1 != father2 {
size1 := this.sizeMap[father1]
size2 := this.sizeMap[father2]
status1 := this.cellingSet[father1]
status2 := this.cellingSet[father2]
if size1 <= size2 {
this.fatherMap[father1] = father2
this.sizeMap[father2] = size1 + size2
if status1 && !status2 || !status1 && status2 {
this.cellingSet[father2] = true
this.cellingAll += twoSelectOne(status1, size2, size1)
}
} else {
this.fatherMap[father2] = father1
this.sizeMap[father1] = size1 + size2
if status1 && !status2 || !status1 && status2 {
this.cellingSet[father1] = true
this.cellingAll += twoSelectOne(status1, size2, size1)
}
}
}
}
}
func (this *UnionFind) valid(row int, col int) bool {
return row >= 0 && row < this.N && col >= 0 && col < this.M && this.grid[row][col] == 1
}
func (this *UnionFind) cellingNum() int {
return this.cellingAll
}
func (this *UnionFind) finger(row int, col int) int {
this.grid[row][col] = 1
cur := row*this.M + col
if row == 0 {
this.cellingSet[cur] = true
this.cellingAll++
}
this.fatherMap[cur] = cur
this.sizeMap[cur] = 1
pre := this.cellingAll
this.union(row, col, row-1, col)
this.union(row, col, row+1, col)
this.union(row, col, row, col-1)
this.union(row, col, row, col+1)
now := this.cellingAll
if row == 0 {
return now - pre
} else {
return twoSelectOne(now == pre, 0, now-pre-1)
}
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
