DFS实现Flood Fill时分支遍历错误的原因排查

我在学习动态规划时尝试解决LeetCode的Flood Fill问题，最初的DFS方案无法正确遍历所有可行路径：当输入image=[[1,1,1],[1,1,0],[1,0,1]]、sr=1、sc=1、color=2时，得到错误结果[[2,2,1],[2,2,0],[1,0,1]]。

错误的DFS代码 #

def floodFill(
    self, image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
    m = len(image) - 1
    n = len(image[0]) - 1
    basecolor = image[sr][sc]
    self.dfs(image, sr, sc, color, basecolor, m, n)
    return image

def dfs(self, image, sr, sc, color, basecolor, m, n):
    if sr < 0 or sr > m or sc < 0 or sc > n:
        return
    if image[sr][sc] == color:
        return
    if image[sr][sc] != basecolor:
        return
        
    image[sr][sc] = color
    for direc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        sr = sr + direc[0]
        sc = sc + direc[1]
        self.dfs(image, sr, sc, color, basecolor, m, n)

修正后的DFS代码（可得到正确结果[[2,2,2],[2,2,0],[2,0,1]]） #

def floodFill(
    self, image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
    m = len(image) - 1
    n = len(image[0]) - 1
    basecolor = image[sr][sc]
    self.dfs(image, sr, sc, color, basecolor, m, n)
    return image

def dfs(self, image, sr, sc, color, basecolor, m, n):
    if sr < 0 or sr > m or sc < 0 or sc > n:
        return
    if image[sr][sc] == color:
        return
    if image[sr][sc] != basecolor:
        return
        
    image[sr][sc] = color
    for direc in [(sr-1, sc), (sr, sc-1), (sr+1, sc), (sr, sc+1)]:
        sr = direc[0]
        sc = direc[1]
        self.dfs(image, sr, sc, color, basecolor, m, n)

错误原因解析 #

核心问题是循环中修改了原sr和sc变量的值，导致后续循环迭代使用的是已经被修改后的坐标，而非初始的当前节点坐标。

拿错误代码里的循环举例：
初始时当前节点是(sr=1, sc=1)。

• 第一次循环：direc=(-1,0)，计算得到sr=1-1=0，sc=1+0=1，递归调用dfs(0,1,...)。这一步没问题。
• 第二次循环：此时sr已经是0，sc是1，再加上direc=(0,-1)，得到sr=0+0=0，sc=1-1=0，但这不是从原节点(1,1)向左移动的(1,0)，而是从(0,1)向左移动的(0,0)，完全偏离了原本要遍历的方向。
• 后续的第三次、第四次循环都会基于前一次修改后的sr/sc计算，自然无法正确遍历当前节点的四个邻接方向，导致部分区域没有被染色，出现错误结果。

而修正后的代码中，每个direc都是直接基于当前节点的原始sr和sc计算得到的邻接坐标，循环中虽然也赋值给了sr和sc，但每次循环的direc都是独立基于初始值生成的，不会互相干扰，因此能正确遍历四个方向的邻接节点，完成完整的Flood Fill。

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