为什么 FloodFill 算法超过了 Leetcode 的最大递归限制？

Question

我正在使用与非常流行的 岛屿数量 问题相同的逻辑来研究 floodfill 算法。因此，当我 运行 带有示例输入的代码时，此解决方案有效，但一旦我提交，它就会显示 Recursion Error: maximum recursion depth exceeded in comparison。

我怎样才能做得更好？我觉得不错，但我知道有问题。

def floodfill(grid,sr,sc,newColor):
    og= grid[sr][sc]

    recurse(grid,sr,sc,newColor,og)
    return grid




def recurse(grid,sr,sc,newColor,og):
    if grid[sr][sc]!= og:
        return


    grid[sr][sc] = newColor
    if sr !=0:
        recurse(grid,sr-1,sc,newColor,og)

    if sc !=0:
        recurse(grid,sr,sc-1,newColor,og)

    if sc != len(grid[0])-1:
        recurse(grid,sr,sc+1,newColor,og)

    if sr != len(grid)-1:
        recurse(grid,sr+1,sc,newColor,og)


floodfill([[1,1,1],[1,1,0],[1,0,1]],1,1,2)

Answer 1

我相信代码适用于 newColor != og 的情况。但我的猜测是你看到了你的错误，因为在 newColor == og 的情况下，停止条件

if grid[sr][sc]!= og:
        return

永远不会发生，导致 recurse 无限递归。这可以通过在您的 floodfill 方法中为此边缘情况添加检查来解决。