求解黑白网格中黑色连通形状的最大边框问题

问题定义 #

• 给定n行m列的网格，单元格为白色（.）或黑色（#）
• 黑色单元格构成无孔洞的连通集合（仅通过共享边连通）
• 边框定义：任意行或列中，无白色单元格间隔的连续黑色单元格的最大数量

解法思路 #

因为黑色形状是连通且无孔洞的，但我们要找的是所有行、列中最长的连续黑块，所以无需额外判断连通性，直接遍历所有行和列即可：

1. 遍历每一行，逐单元格统计连续黑色单元格的长度，记录当前最大值
2. 遍历每一列，逐单元格统计连续黑色单元格的长度，更新最大值
3. 最终的最大值就是所求的最大边框

代码实现（Python） #

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]
    max_border = 0
    
    # 统计每行的最长连续黑块
    for row in grid:
        current_len = 0
        for cell in row:
            if cell == '#':
                current_len += 1
                if current_len > max_border:
                    max_border = current_len
            else:
                current_len = 0
    
    # 统计每列的最长连续黑块
    for col_idx in range(m):
        current_len = 0
        for row_idx in range(n):
            if grid[row_idx][col_idx] == '#':
                current_len += 1
                if current_len > max_border:
                    max_border = current_len
            else:
                current_len = 0
    
    print(max_border)

代码说明 #

• 先读取测试用例总数，逐个处理每个测试用例
• 读取网格的行数n和列数m，再读取完整的网格内容
• 分别对行和列进行遍历，实时统计连续黑块的长度，一旦遇到白色单元格就重置计数器
• 每次统计时更新全局的最大边框值，最后输出结果

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