二维二进制数组孔洞检测问题（Python实现方向咨询）

核心逻辑 #

孔洞指的是完全被1包围、不接触数组边界的连通0区域。解决思路的关键是：先清除所有与数组边界连通的0区域，剩下的未被清除的0区域就是孔洞——只要存在这类区域，就说明数组里有孔洞。

具体实现步骤 #

• 第一步：清理边界连通的0区域
  遍历数组的四条边界（第一行、最后一行、第一列、最后一列），遇到0就用DFS或BFS遍历其所有连通的0，将这些0全部标记为1（或标记为已访问），彻底清除所有与外界连通的0。
• 第二步：检查剩余0的存在
  遍历处理后的数组，若还存在0，则说明这些0是被1完全包围的孔洞区域，直接返回True；若遍历后无0，返回False。

Python代码示例 #

def has_hole(grid):
    if not grid or not grid[0]:
        return False
    
    rows, cols = len(grid), len(grid[0])
    
    # DFS遍历并清除连通的0
    def dfs(i, j):
        # 越界或当前不是0则返回
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != 0:
            return
        grid[i][j] = 1  # 标记为已处理
        # 递归处理上下左右四个方向的连通节点
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    # 处理第一行和最后一行的所有列
    for j in range(cols):
        if grid[0][j] == 0:
            dfs(0, j)
        if grid[rows - 1][j] == 0:
            dfs(rows - 1, j)
    
    # 处理第一列和最后一列（跳过已处理的首尾行）
    for i in range(1, rows - 1):
        if grid[i][0] == 0:
            dfs(i, 0)
        if grid[i][cols - 1] == 0:
            dfs(i, cols - 1)
    
    # 检查是否还有剩余的0（即孔洞）
    for row in grid:
        if 0 in row:
            return True
    return False

补充说明 #

• 除了DFS，也可以用BFS（队列实现）处理连通区域，逻辑一致，可根据习惯选择。
• 代码中直接修改原数组是为了节省空间，若不想修改原数组，可创建一个与原数组同大小的布尔矩阵，记录已访问的0节点。
• 边界处理时，首尾行遍历所有列，中间行仅处理首尾列，避免重复操作。

内容的提问来源于stack exchange，提问作者Chris