803. Bricks Falling When Hit #

题目 #

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:

• The number of rows and columns in the grid will be in the range [1, 200].
• The number of erasures will not exceed the area of the grid.
• It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
• An erasure may refer to a location with no brick - if it does, no bricks drop.

题目大意 #

我们有一组包含1和0的网格；其中1表示砖块。 当且仅当一块砖直接连接到网格的顶部，或者它至少有一块相邻（4 个方向之一）砖块不会掉落时，它才不会落下。我们会依次消除一些砖块。每当我们消除 (i, j) 位置时， 对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这个消除而落下。返回一个数组表示每次消除操作对应落下的砖块数目。

注意:

• 网格的行数和列数的范围是[1, 200]。
• 消除的数字不会超过网格的区域。
• 可以保证每次的消除都不相同，并且位于网格的内部。
• 一个消除的位置可能没有砖块，如果这样的话，就不会有砖块落下。

解题思路 #

• 有一些砖块连接在天花板上，问，如果打掉某个砖块，会掉落几块砖块？打掉的每个砖块不参与计数。
• 这一题可以用并查集和 DFS 求解。不过尝试用 DFS 的同学就会知道，这一题卡时间卡的很紧。用 DFS 虽然能 AC，但是耗时非常长。用并查集也必须进行秩压缩，不然耗时也非常长。另外，如果用了并查集，每个集合的总数单独统计，不随着 union() 操作，也会导致超时，笔者在这里被 LTE 了多次，最后只能重写 UnionFind 并查集类，将统计操作和 union() 操作写在一起，这一题才 faster than 100.00% AC。
• 拿到题以后，首先尝试暴力解法，按照顺序打掉砖块，每次打掉砖块以后，都重建并查集。题目要求每次掉落几块砖块，实际上比较每次和天花板连通的砖块个数变化了多少块就可以了。那么解法就出来了，先把和天花板连通的砖块都 union() 起来，记录这个集合中砖块的个数 count，然后每次打掉一个砖块以后，重建并查集，计算与天花板连通的砖块的个数 newCount，newCount - count -1 就是最终答案(打掉的那块砖块不计算其中)，提交代码以后，发现 TLE。
• 出现 TLE 以后一般思路都是对的，只是时间复杂度过高，需要优化。很明显，需要优化的地方是每次都重建了新的并查集，有没有办法能在上一次状态上进行变更，不用重建并查集呢？如果正向的打掉砖块，那么每次还需要以这个砖块为起点进行 DFS，时间复杂度还是很高。如果反向考虑呢？先把所有要打掉的砖块都打掉，构建打掉这些砖块以后剩下与天花板连通的并查集。然后反向添加打掉的砖块，每次添加一块就刷新一次它周围的 4 个砖块，不用 DFS，这样时间复杂度优化了很多。最后在按照 newCount - count -1 方式计算最终答案。注意每次还原一个砖块的时候需要染色回原有砖块的颜色 1 。优化成这样的做法，基本不会 TLE 了，如果计算 count 是单独计算的，还是会 TLE。如果没有进行秩压缩，时间会超过 1500 ms，所以这一题想拿到 100%，每步优化都要做好。最终 100% 的答案见代码。

代码 #

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)
	// 先将要打掉的砖块染色
	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)
		}
	}
}