Go游戏fill_reaching方法问题：洪水填充算法返回结果不符预期

常见问题排查 #

首个测试用例通常是最简场景（比如单个单元格、起点即为目标颜色），出现返回False的问题，大概率是代码未正确处理起点本身：

• 跳过了起点的颜色检查，直接去遍历相邻单元格
• 未将起点标记进visited矩阵
• 初始判断逻辑错误，未识别起点本身就是目标颜色的情况

修正后的代码 #

根据你的需求（标记与起点连通的同色区域，返回起点是否可达指定颜色），以下是修正后的fill_reaching实现：

class Board:
    def __init__(self, grid):
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0]) if self.rows > 0 else 0

    def fill_reaching(self, start_row, start_col, target_color, visited):
        # 先校验起点坐标合法性
        if not (0 <= start_row < self.rows and 0 <= start_col < self.cols):
            return False
        
        start_color = self.grid[start_row][start_col]
        # 初始化：起点是否为目标颜色
        found = self.grid[start_row][start_col] == target_color
        # 如果起点已访问，直接返回当前found结果（避免重复处理）
        if visited[start_row][start_col]:
            return found
        
        # 洪水填充：标记所有连通的同起点色单元格
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        stack = [(start_row, start_col)]
        visited[start_row][start_col] = True

        while stack:
            row, col = stack.pop()
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                # 校验相邻单元格的合法性、未访问状态、颜色是否与起点一致
                if 0 <= nr < self.rows and 0 <= nc < self.cols:
                    if not visited[nr][nc] and self.grid[nr][nc] == start_color:
                        visited[nr][nc] = True
                        stack.append((nr, nc))
                        # 检查当前单元格是否为目标颜色
                        if self.grid[nr][nc] == target_color:
                            found = True
        
        return found

关键修正点 #

1. 优先处理起点：先检查起点坐标合法性，直接判断起点是否为目标颜色，初始化found状态
2. 避免重复处理：如果起点已被标记为访问，直接返回结果
3. 正确的洪水填充逻辑：只遍历与起点同色的连通单元格，标记visited的同时检查是否命中目标颜色
4. 循环终止条件清晰：用栈实现迭代式洪水填充，避免递归深度问题

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