1

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

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

它代表一种带有不同颜色区域的地图。上面的示例显示了四个不同的区域，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

我知道我在这里缺少一些基本的东西。我基本上是在说“这是当前角色，现在看每个方向看它是否具有相同的角色。”

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

谢谢你的帮助。

4

3 回答 3

3

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

一旦计算了一个方格，就不能再次计算它（这包括通过递归调用来计算countArea()！）

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

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

于 2012-12-11T19:56:16.927 回答
1

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

方法一

在仍然使用递归的同时克服这个问题的一种方法是指定递归应该寻找更多相同类型字段的方向。例如，调用第一个字段的正北（或上方）可能会递归地看起来更远的北方或东方（或右边），向东的那个向南（下方）和东方等等。

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

存在更多这样的算法也能够解决上述问题。看看维基百科上的洪水填充。

方法二

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

于 2012-12-11T19:57:20.100 回答
1

以下实现应该有效：

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

例子：

>>> print '\n'.join(''.join(row) for row in map)
...AAA....
...AAABB..
..BBBBBCC.
.....CCCC.
.DDD..CC..
.DDD......
>>> countArea(map, 5, 2)
6
>>> countArea(map, 2, 8)
8

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

A.
.A

附带说明一下，您不应将map其用作变量名，因为它会掩盖内置map()函数。

于 2012-12-11T20:08:21.893 回答