0

特定の 2 次元配列内の島の数を計算する必要がある checkio タスクを解決しようとしています。島は、水平、斜め、または垂直に接続された「1」のグループとして定義されます ( http:/ /www.checkio.org/mission/task/info/calculate-islands/python-3/ )。私が書いたコードは、位置の数が0の場合、最初に検索空間から位置を削除することになっています(正しい言葉を使用しているかどうかはわかりません。アルゴリズムについては何も知りません)。問題は、コードが番号 0 を持ついくつかの位置のみを削除し、0 を持つ他の位置を削除しないことです。コードは次のとおりです。

def checkio(data):

    result = ''
    count = 0
    boo = True
    searchspace = []
    specificsearchspace = []
    def search(y,x):
            result = ''
            count = 0
            if data[y][x] == 0:
                searchspace.remove([y,x])
            if data[y][x] == 1:
                specificsearchspace.extend([[y,x+1],[y+1,x-1],[y+1,x],[y+1,x+1]])
                for i in specificsearchspace:
                    if data[i[0]][i[1]] == 0:
                        searchspace.remove(i)
                        specificsearchspace.remove(i)
                    if data[i[0]][i[1]] == 1:
                        searchspace.remove(i)
                        specificsearchspace.remove(i)
                        count += 1
                        search(i[0],i[1])
                result += str(count) + ','
                return result
    for y in range(len(data)):
        for x in range(len(data[y])):
            searchspace.append([y,x])
    print searchspace
    for f in searchspace:
        print search(f[0],f[1])
    print searchspace

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio([[0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 0],
                    [0, 0, 0, 1, 0],
                    [0, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0]]) == [1, 3], "1st example"
    assert checkio([[0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 0],
                    [0, 0, 0, 1, 0],
                    [0, 1, 1, 0, 0]]) == [5], "2nd example"
    assert checkio([[0, 0, 0, 0, 0, 0],
                    [1, 0, 0, 1, 1, 1],
                    [1, 0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4], "3rd example"

出力は次のとおりです。

[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4]]
None
None
None
None
1,
None
None
None
None
None
[[0, 1], [0, 3], [1, 0], [1, 2], [1, 3], [2, 1], [3, 1], [4, 0], [4, 2], [4, 4]]
4

1 に答える 1

3

.remove() を呼び出すたびに、リストを反復しながらリストのサイズを変更しているためです。

これの非常に小さな例として、これを試してみてください:

items = [1, 2, 3, 4, 5]

for item in items:
    if item == 2:
        items.remove(item)

    print item

これで 1、2、4、5 が表示されることがわかります。3 はどこに行ったのでしょうか。何が起こったのかというと、Python はリスト内の反復した場所へのポインターを保持していましたが、そのポインターの下でリストが変更されました。誰かの下から敷物を引き抜くようなものです。

これに取り組む良い方法がいくつかあります。長さからゼロまで逆方向にループするか、remove() を実行するたびにインデックスから 1 を引くことができます。また、while ループを実行して、「このループ中にゼロがいくつか見つかりました」というフラグを設定し、そのフラグが false の場合は、while ループを終了することもできます。あまり効率的ではありませんが、効果的です。

于 2013-07-03T17:53:45.090 に答える