1

次のような Python (バージョン 3.2) の 2D 配列があります。

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

これは、さまざまな色で塗りつぶされた領域を持つ一種の地図を表しています。上記の例は、A、B、C、および D の 4 つの異なる領域を示しています。

配列のインデックス付けの例を次に示します。 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()! の再帰呼び出しによるカウントが含まれます)。

現在のアルゴリズムは可能な限り北に進み、南に 1 歩進んだ後、北に 1 歩進みます。この 2 段階のシーケンスは、スタック領域がなくなるまで繰り返されます。

必要に応じて、ウィキペディアでこの問題のアルゴリズムを読むことができます。

于 2012-12-11T19:56:16.927 に答える
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 に答える
1

あなたのコードでは、アルゴリズムは特定の入力フィールドの左の 1 つのフィールドを調べ、再帰呼び出しでは最初のフィールドで関数を再度呼び出します。（無限再帰につながるため、明らかに望ましくないもの）

アプローチ1

再帰を使用しながらこの問題を解決する方法は、再帰が同じタイプのフィールドをさらに探す方向を指定することです。たとえば、最初のフィールドのすぐ北 (または上) のフィールドへの呼び出しは、北または東 (または右) に再帰的に遠くに見える可能性があり、東へのフィールドは南 ( below ) および東などに移動します。

最初のステップを賢く選択することで、スキャンした領域に重複がないことを確認できます。ただし、再帰呼び出しがスキャンする方向を指定するには、いくつかの調整が必要です。ただし、このアルゴリズムは、エリアが張り出している場合は機能しないことに注意してください。したがって、開始点の北東にあるすべてのフィールドに右と上に移動するだけでは到達できません。

上記の問題を解決できる、このようなアルゴリズムが他にもあります。ウィキペディアの Flood Filling をご覧ください。

アプローチ 2

また、何らかの方法で既にアクセスしたフィールドを保存し、フィールドが既にアクセスされている場合は再帰呼び出しから直接戻ることもできます。

于 2012-12-11T19:57:20.100 に答える