website/content.en/ChapterFour/0800~0899/0803.Bricks-Falling-When-Hit.md
We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.
We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.
Return an array representing the number of bricks that will drop after each erasure in sequence.
Example 1:
Input:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation:
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input:
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation:
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.
Note:
We have a grid containing 1s and 0s; 1 represents a brick. A brick will not fall if and only if it is directly connected to the top of the grid, or at least one of its adjacent bricks (in one of the 4 directions) will not fall. We will remove some bricks in sequence. Whenever we remove the position (i, j), the brick at the corresponding position (if it exists) disappears, and then other bricks may fall because of this removal. Return an array representing the number of bricks that fall after each removal operation.
Note:
count, and then after knocking out a brick each time, rebuild the Union-Find and calculate the number of bricks connected to the ceiling as newCount. newCount - count -1 is the final answer (the knocked-out brick is not counted). After submitting the code, it TLEs.newCount - count -1. Note that each time a brick is restored, it needs to be colored back to the original brick color 1. With this optimization, it basically will not TLE. If count is calculated separately, it will still TLE. If rank compression is not performed, the time will exceed 1500 ms, so for this problem, if you want to get 100%, every optimization step must be done well. The final 100% answer is shown in the code.
package leetcode
import (
"github.com/halfrost/leetcode-go/template"
)
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)
// First mark the bricks to be hit
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)
}
}
}