如何在Python数组中检测被1完全包围的2的群组？

核心思路 #

• 先排除所有位于数组边缘，或与边缘2连通的2：这类2没有被1完全包围，不计入统计
• 剩余未被标记的2的连通群组，就是完全被1包围的目标群组，统计其数量即可

实现步骤 #

1. 遍历数组的四条边缘（第一行、最后一行、第一列、最后一列），遇到值为2的单元格，用BFS（广度优先搜索）遍历所有和它连通的2，标记为已访问
2. 遍历整个数组，每遇到未被标记的2，计数加1，同时用BFS标记该群组的所有2，避免重复统计

代码实现（Python） #

def count_surrounded_twos(grid):
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    # 记录已处理的2的位置
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    # 上下左右四个移动方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # BFS遍历连通的2区域并标记
    def bfs(x, y):
        queue = [(x, y)]
        visited[x][y] = True
        while queue:
            cx, cy = queue.pop(0)
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                # 检查坐标是否在数组范围内，且未访问、值为2
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and grid[nx][ny] == 2:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    
    # 处理第一行和最后一行的边缘2
    for y in range(cols):
        if grid[0][y] == 2 and not visited[0][y]:
            bfs(0, y)
        if grid[rows-1][y] == 2 and not visited[rows-1][y]:
            bfs(rows-1, y)
    
    # 处理第一列和最后一列的边缘2（排除已处理的行首行尾）
    for x in range(1, rows-1):
        if grid[x][0] == 2 and not visited[x][0]:
            bfs(x, 0)
        if grid[x][cols-1] == 2 and not visited[x][cols-1]:
            bfs(x, cols-1)
    
    # 统计被包围的2的群组数量
    count = 0
    for x in range(rows):
        for y in range(cols):
            if grid[x][y] == 2 and not visited[x][y]:
                count += 1
                bfs(x, y)
    
    return count

# 测试示例数组
test_grid = [
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2],
    [2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2],
    [2,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,2,2],
    [1,1,2,2,1,1,1,1,2,2,2,1,1,1,2,2,1,1,1,2],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
]

print(count_surrounded_twos(test_grid))  # 输出3，符合预期

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