在Python中的地图着色算法

Question

我在Python（3.2版）中有一个2D数组，如下所示：

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

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

以下是索引数组的示例： map[1][5]=='A'将返回True。在

我试图编写一个函数，它接受这样一个数组和一个行/列索引，并返回具有相同“颜色”的相邻空格数。因此，使用上面的示例，下面是一些返回值（参数分别是数组、行和列号：

^{pr2}$

我想把它作为递归函数来实现，但是我搞不懂。以下是我目前所掌握的情况：

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

在您的代码中，算法将查找给定输入字段左侧的一个字段，而在递归调用中，将再次调用初始字段上的函数。（你显然不想要的，因为它会导致无限递归）

方法1

在仍然使用递归的情况下解决这个问题的一种方法是指定一个方向，递归应该在该方向查找更多相同类型的字段。例如，对第一个字段的正北方（或上面的）的调用可以递归地向北或东（或右），向东的调用向南（低于）和以东，依此类推。在

通过智能地选择第一步，您可以确保扫描区域中没有重叠。但是，它需要一些调整来指定递归调用应该扫描的方向。但是：请注意，如果区域悬垂，则此算法将不起作用，因此，如果不是，只需向右和向上移动就可以到达起点东北部的每个区域。在

有更多类似这样的算法也能解决上述问题。看看Flood Filling on wikipedia。在

方法2

您还可以以某种方式保存已经访问过的字段，如果字段已经访问过，则直接从递归调用返回。在

Answer 2

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

一旦一个网格正方形被计数，它就不能再被计数（这包括通过递归调用countArea()！）在

你当前的算法尽量往北走，然后继续向南走一步，然后再往北走一步。这个两步序列重复，直到堆栈空间用完为止。在

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

Answer 3

以下实施应有效：

def countArea(map, row, col, key=None, seen=None):
    if key is None:
        key = map[row][col]
    if seen is None:
        seen = set()
    seen.add((row, col))  # mark this location as visited
    n = 1
    for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
         r, c = row + dy, col + dx
         if r < 0 or r >= len(map) or c < 0 or c >= len(map[0]):  # check boundaries
             continue
         # only increment and recurse if key matches and we haven't already visited
         if map[r][c] == key and (r, c) not in seen:
             n += countArea(map, r, c, key, seen)
    return n

示例：

^{pr2}$

请注意，这假设具有相同键且仅在对角线处接触的区域应视为独立的，例如，对于以下映射countArea(map, 0, 0)和countArea(map, 1, 1)都将返回1：

A.
.A

另外，您不应该使用map作为变量名，因为它将屏蔽内置的map()函数。在