August 20, 2021: brick making. There is a binary grid of m x n, where 1 table

2021-08-20： Brick making . There is one m x n The binary mesh of , among 1 For bricks ,0 It means blank . brick Stable （ It won't fall ） The premise is ：1. A brick is connected directly to the top of the grid , perhaps ,2. There's at least one adjacent （4 One of the directions ） brick Stable When it doesn't fall . Give you an array hits , This is where the bricks need to be removed in turn . Whenever eliminated hitsi = (rowi, coli) A brick in position , Bricks in the corresponding positions （ If exist ） Will disappear , Then other bricks may fall due to this elimination operation . Once a brick falls , It will immediately disappear from the grid （ namely , It doesn't fall on other stable bricks ）. Returns an array result , among resulti It means the first one i The number of bricks dropped corresponding to one elimination operation . Be careful , Elimination may point to a blank space without bricks , If this happens , No bricks fall .

Fuda answer 2021-08-20：

Union checking set . Converse thinking .

The code to use golang To write . The code is as follows ：

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
}

//  Union checking set 
type UnionFind struct {
    N int
    M int
    //  How many bricks are there , Connected to the ceiling 
    cellingAll int
    //  Original matrix , Because of the impact of shells ,1 -> 2
    grid [][]int
    // cellingSet[i] = true; i  It's the head node , The collection is the ceiling collection 
    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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code