0803：打砖块（2765 分）

2017-03-13 约 845 字预计阅读 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
41
42


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

752 ms

目录

0803：打砖块（2765 分）

题目

分析

解答