打砖块

标签: 并查集 数组 矩阵

难度: Hard

有一个 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 * 104
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • 所有 (xi, yi) 互不相同

Submission

运行时间: 167 ms

内存: 23.2 MB

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        def dfs(i,j):
            if i<0 or i==n or j<0 or j==m or grid[i][j]!=1:
                return 0
            grid[i][j]=2
            return 1+dfs(i-1,j)+dfs(i+1,j)+dfs(i,j-1)+dfs(i,j+1)
        
        def worth(x,y):
            if x==0:
                return True
            if x-1>=0 and grid[x-1][y]==2:
                return True
            if x+1<n and grid[x+1][y]==2:
                return True
            if y-1>=0 and grid[x][y-1]==2:
                return True
            if y+1<m and grid[x][y+1]==2:
                return True
            return False
                
        n,m=len(grid),len(grid[0])
        l=len(hits)
        res=[0]*l
        for x,y in hits:
            grid[x][y]-=1
        for j in range(m):
            if grid[0][j]==1:
                dfs(0,j)
        for i in range(l-1,-1,-1):
            x,y=hits[i]
            grid[x][y]+=1
            if grid[x][y]==1 and worth(x,y):
                res[i]=dfs(x,y)-1
        return res

Explain

这道题的思路是使用并查集和逆向思维。首先，我们将所有的hit操作预先执行，将对应位置的砖块标记为已消除状态。然后从网格的顶部开始进行深度优先搜索，将所有与顶部连通的砖块标记为稳定状态。接下来，我们逆序遍历hits数组，依次将砖块还原。对于每个还原的砖块，我们判断其是否与稳定的砖块相邻或者位于顶部，如果是，则进行深度优先搜索，将与其连通的不稳定砖块都标记为稳定状态，并记录下变为稳定状态的砖块数量。最后返回每次还原操作导致掉落的砖块数量。

时间复杂度: O(l * nm)

空间复杂度: O(nm)

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        def dfs(i,j):
            if i<0 or i==n or j<0 or j==m or grid[i][j]!=1:
                # 越界或者当前位置不是砖块，返回0
                return 0
            grid[i][j]=2  # 将当前砖块标记为稳定状态
            # 递归搜索上下左右四个方向，并将结果相加
            return 1+dfs(i-1,j)+dfs(i+1,j)+dfs(i,j-1)+dfs(i,j+1)
        
        def worth(x,y):
            if x==0:  # 如果砖块在顶部，返回True
                return True
            # 判断砖块的上下左右是否有稳定的砖块
            if x-1>=0 and grid[x-1][y]==2:
                return True
            if x+1<n and grid[x+1][y]==2:
                return True
            if y-1>=0 and grid[x][y-1]==2:
                return True
            if y+1<m and grid[x][y+1]==2:
                return True
            return False
                
        n,m=len(grid),len(grid[0])
        l=len(hits)
        res=[0]*l
        for x,y in hits:
            grid[x][y]-=1  # 预处理hits数组，将对应位置的砖块标记为已消除状态
        for j in range(m):
            if grid[0][j]==1:  # 从网格顶部开始搜索稳定的砖块
                dfs(0,j)
        for i in range(l-1,-1,-1):  # 逆序遍历hits数组
            x,y=hits[i]
            grid[x][y]+=1  # 还原砖块
            if grid[x][y]==1 and worth(x,y):  # 如果还原后的砖块与稳定砖块相邻或位于顶部
                res[i]=dfs(x,y)-1  # 进行深度优先搜索，并记录变为稳定状态的砖块数量
        return res

Explore

在算法中，将grid中的值从1改为2是用来区分未访问的砖块和已确认为稳定的砖块。原始的1表示砖块存在但尚未确认其稳定性，而2表示该砖块已经被访问过，并且确认与顶部直接或间接相连，因此是稳定的。这种区分有助于在后续的递归搜索中避免重复访问同一个砖块，从而优化算法的效率。

算法预设所有hits操作都是有效的，即hits数组中的每个位置都有砖块存在。因此，在预处理阶段，直接将对应位置的砖块值减1（即从1变为0）以模拟砖块被击中并消除的效果。这个假设简化了代码的复杂度，避免了不必要的检查。如果有必要处理无效的hits（比如原位置没有砖块的情况），则需要在代码中添加额外的逻辑来验证每个hit的有效性。

在每次还原操作中，我们首先检查被还原的砖块是否能与稳定砖块相连。如果可以，我们通过深度优先搜索（DFS）将所有与之相连的不稳定砖块标记为稳定。在这个过程中，DFS函数返回的是所有通过此次搜索变为稳定的砖块数量，包括被还原的那一块砖本身。因此，为了准确计算由于这次还原操作额外导致的掉落（变稳定）的砖块数量，需要从DFS的结果中减去1，即除去被还原的那块砖本身。

在递归深度优先搜索中，首先会检查当前坐标是否越界（即是否超出grid的行或列范围），以及当前位置的砖块状态。如果当前位置越界或者不是未访问的砖块（即状态不是1），则DFS直接返回0并终止当前路径的搜索。同时，为了避免重复访问已经标记为稳定的砖块（状态为2），一旦某个砖块在DFS过程中被验证为稳定，其状态就会从1变为2。这样，后续的DFS调用遇到状态为2的砖块时，会直接返回0，从而有效避免重复访问。这些措施确保了DFS的效率和正确性。