递归 - 洪水填充算法

Question

我需要编写一个泛洪填充算法，用于在较大的代码中填充洞穴的特定单元格，并根据它们所在的房间使用不同颜色的水进行填充。

由于某种原因，我的递归算法不起作用，并且一直告诉我超过了最大递归深度，我不知道为什么。

我正在尝试逐个单元格地进行操作，检查它是AIR、STONE还是WATER，如果它是STONE或WATER，我希望它不做任何操作。如果它是AIR，我希望它填充该单元格。

有人能给我一些提示或建议吗？

#flood fill algorithm
def fill(cave, row, col, color):

    caveWidth = len(cave)
    caveHeigth = len(cave[0])


    if row > 0:
        fill(cave, row-1, col, color) #left
    if col > 0:
        fill(cave, row, col-1, color) #up
    if row < caveWidth-1:
        fill(cave, row+1, col, color) #right
    if col < caveHeigth-1:
        fill(cave, row, col+1, color) #down

    if cave[row][col] == STONE or cave[row][col] == WATER:
        return

    if cave[row][col] == AIR : 
        cave[row][col] = WATER
        grid.fill_cell(row, col, color)

- Colter Therrell

---

这最好通过迭代而不是递归来完成。这样会更快，更高效。 - daniel gratzer

@jozefg：实现一个正确的快速泛洪填充算法不是很困难吗？ - krlmlr

行和列是有符号的还是无符号的？ - 001

@user946850 是的...虽然广度优先搜索版本更节省空间，并且也避免了递归。只需使用队列即可，而不是调用栈。 - daniel gratzer

Answer 1

在fill程序的开始处打印row和col，以查看问题所在。稍微调整一下代码，就没问题了 :-)

- krlmlr

Answer 2

不要使用递归算法，它们是魔鬼的玩物。

维基百科列出了各种实用算法，如扫描线填充。

- Tyler Durden

---

递归是许多实际问题的完美工具。即使扫描线填充通常也是使用显式堆栈而不是线程堆栈实现的递归解决方案。 - Adrian McCarthy

@TylerDurden：那么什么是函数式语言呢？邪恶的化身吗？;-) - krlmlr