题目描述：

LeetCode 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.

题目大意：

二维01矩阵grid表示砖墙，1表示砖块，0表示空白。

当砖块失去位于顶部的砖块互相连通时，就会被抹除。

按顺序hits抹除一些砖块，求每一次抹除后会连带多少砖块被抹除。

解题思路：

逆序遍历hits + 并查集 + BFS

Python代码：

class Solution(object):
    def hitBricks(self, grid, hits):
        """
        :type grid: List[List[int]]
        :type hits: List[List[int]]
        :rtype: List[int]
        """
        
        parents = {0 : 0}
        gcnts = {0 : 0}
        h, w = len(grid), len(grid[0])

        def father(i):
            while parents[i] != i:
                i = parents[i]
            return i
        
        def union(a, b):
            a = father(a)
            b = father(b)
            if a == b: return
            if a > b: a, b = b, a
            parents[b] = a
            gcnts[a] += gcnts[b]
        
        def fidx(x, y):
            return x * w + y + 1

        for x in range(h):
            for y in range(w):
                if not grid[x][y]: continue
                idx = fidx(x, y)
                gcnts[idx] = 1
                parents[idx] = idx

        for x, y in hits: grid[x][y] -= 1
        
        def neighbors(x, y):
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] > 0:
                    yield nx, ny

        def bfs(x, y):
            q = [(x, y)]
            while q:
                x, y = q.pop(0)
                idx = fidx(x, y)
                for nx, ny in neighbors(x, y):
                    nidx = fidx(nx, ny)
                    if father(idx) != father(nidx):
                        union(idx, nidx)
                        q.append((nx, ny))

        for y in range(w):
            if grid[0][y] == 1:
                union(fidx(0, y), 0)
                bfs(0, y)

        cnt = gcnts[0]
        ans = []
        for x, y in hits[::-1]:
            if grid[x][y] < 0:
                ans.append(0)
            else:
                p = father(fidx(x, y))
                if x == 0 and p > 0: union(p, 0)
                grid[x][y] = 1
                bfs(x, y)
                delta = gcnts[0] - cnt
                ans.append(max(delta - 1, 0))
                cnt = gcnts[0]
        return ans[::-1]

 

本文链接：http://bookshadow.com/weblog/2018/03/26/leetcode-bricks-falling-when-hit/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码