如何用Python统计字符矩阵中连通的%块（补丁）数量？

这是典型的连通分量计数问题，用DFS（深度优先搜索）或者BFS（广度优先搜索）就能轻松解决。核心逻辑是：遍历矩阵的每一个位置，遇到未被访问过的%时，就启动一次搜索，把所有和它连通的%都标记为已访问，每完成一次这样的搜索就代表找到一个新的补丁，最后统计搜索的次数就是补丁总数。

实现步骤 #

1. 输入处理与初始化

   • 将输入的多行字符串转换为二维列表，方便后续修改和访问。
   • 创建一个和原矩阵大小相同的visited矩阵，用来记录每个位置是否已经被处理过，避免重复统计。

2. 连通块搜索（以DFS为例）

   • 定义一个DFS函数，传入当前位置的行号和列号：
     • 如果当前位置超出矩阵边界、是.或者已经被访问过，直接返回。
     • 标记当前位置为已访问。
     • 递归处理当前位置的上下左右四个方向（如果需要支持八连通，只需加上对角线四个方向即可）。

3. 遍历统计

   • 遍历矩阵的每一个位置，当遇到未访问的%时，调用DFS函数，并将补丁计数加1。

完整代码示例 #

def count_patches(matrix):
    if not matrix:
        return 0
    
    rows = len(matrix)
    cols = len(matrix[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    count = 0
    
    # 定义DFS函数
    def dfs(r, c):
        # 边界判断：越界、非%、已访问则返回
        if r < 0 or r >= rows or c < 0 or c >= cols or matrix[r][c] != '%' or visited[r][c]:
            return
        visited[r][c] = True
        # 遍历四个方向
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    # 遍历整个矩阵
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == '%' and not visited[r][c]:
                dfs(r, c)
                count += 1
    
    return count

# 测试示例输入
input_matrix = [
    ".....%%%%%..%",
    "%%%...%%...%%",
    "%.....%%%..%%",
    "...%%.....%%%",
    "....%%.....%%",
    ".....%%%..%%%",
    "%%%%....%%%.."
]

patch_count = count_patches(input_matrix)
print(f"{patch_count} patches.")

代码说明 #

• 运行上述代码，输入示例矩阵会输出4 patches.，和预期结果一致。
• 如果需要支持八连通（即对角线相邻的%也算连通），只需在DFS函数中添加四个对角线方向的递归调用：

  dfs(r+1, c+1)
  dfs(r+1, c-1)
  dfs(r-1, c+1)
  dfs(r-1, c-1)
  

• 空矩阵、全是.或者全是%的边界情况都已处理，保证鲁棒性。

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