2021-08-20：打砖块。有一个 m x n 的二元网格，其中 1 表示砖块，0 表

大家好，欢迎来到IT知识分享网。

2021-08-20：打砖块。有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：1.一块砖直接连接到网格的顶部，或者，2.至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时。给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

福大大 答案2021-08-20：

并查集。逆向思维。

代码用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
    }
}

执行结果如下：

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class13/Code04_BricksFallingWhenHit.java)