python - Python 中的 map 颜色算法

Question

我在 Python(3.2 版)中有一个二维数组，如下所示:

...AAA....
...AAABB..
..BBBBBCC.
.....CCCC.
.DDD..CC..
.DDD......

它代表一种 map ，其中的区域涂有不同的颜色。上面的示例显示了四个不同的区域，A、B、C 和 D。

这是索引数组的示例:map[1][5] == 'A' 会返回 True。

我正在尝试编写一个函数，它接受这样的数组和行/列索引，并返回具有相同“颜色”的相邻空格的数量。所以使用上面的例子，这里有一些返回值(参数分别是数组、行和列号:

6 <-- countArea(map, 5, 2)
8 <-- countArea(map, 2, 8)

我想将其实现为一个递归函数，但我想不通。这是我到目前为止所拥有的:

def countArea(map, row, col):

    key = map[row][col]

    if (map[row-1][col] == key):
        return 1 + countArea(map, row-1, col)
    elif (map[row+1][col] == key):
        return 1 + countArea(map, row+1, col)
    elif (map[row][col+1] == key):
        return 1 + countArea(map, row, col+1)
    elif (map[row][col-1] == key):
        return 1 + countArea(map, row, col-1)
    else:
        return 1

我知道我在这里遗漏了一些基本的东西。我基本上是在说“这是当前字符，现在向各个方向看，看看它是否具有相同的字符。”

我的问题是，我在这个递归定义中遗漏了什么？

感谢您的帮助。

Answer 1

My question is, what am I missing in this recursive definition?

一旦对网格方 block 进行了计数，就不能再次对其进行计数(这包括通过递归调用 countArea() 进行计数!)

您当前的算法尽可能向北移动，然后继续向南移动一步，然后向北移动一步。重复这个两步序列，直到用完堆栈空间。

如果愿意，您可以在 Wikipedia 中阅读有关此问题的算法。 .