0803：打砖块（2765 分）

2017-03-13 约 879 字预计阅读 2 分钟次阅读

力扣第 803 题

题目

有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块稳定不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例 1：

输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。

示例 2：

输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：网格开始为：
[[1,0,0,0],
[1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 10⁴
hits[i].length == 2
0 <= x_i<= m - 1
0 <= y_i <= n - 1
所有 (x_i, y_i) 互不相同

相似问题：

分析

连通相关容易想到并查集，但本题是要去掉元素而不是添加元素
一个巧妙的想法是逆向思维
- 逆向遍历，依次添加砖块，并维护并查集大小
- 那么连到顶部的连通块增加的大小（除了当前添加的砖块外）即为所求
注意消除可能指向空白，所以先记录有效的消除操作

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        def find(x):
            if f[x]!=x:
                f[x] = find(f[x])
            return f[x]
        
        def union(x,y):
            fx, fy = find(x),find(y)
            if fx != fy:
                f[fx] = fy
                sz[fy] += sz[fx]
        
        m,n = len(grid), len(grid[0]) 
        f,dum = list(range(m*n+1)),m*n
        sz = [1]*(m*n+1)
        A = []
        for idx,(i,j) in enumerate(hits):
            if grid[i][j]:
                A.append((idx,i,j))
                grid[i][j] = 0
        for i,j in product(range(m),range(n)):
            if grid[i][j]:
                if i==0:
                    union(j,dum)
                if i and grid[i-1][j]:
                    union(i*n+j,i*n-n+j)
                if j and grid[i][j-1]:
                    union(i*n+j,i*n+j-1)
        res = [0]*len(hits)
        for idx,i,j in A[::-1]:
            tmp = sz[find(dum)]
            if i==0:
                union(j,dum)
            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<=x<m and 0<=y<n and grid[x][y]:
                    union(i*n+j,x*n+y)
            grid[i][j] = 1
            res[idx] = max(0,sz[find(dum)]-tmp-1)
        return res

307 ms

目录

0803：打砖块（2765 分）

题目

分析

解答