どのように再帰を使用してグリッド内の接続されたセルを見つけるのですか？</p> <p>：

Question

私は、次のようなグリッドを与える問題をやっていますn =行数、m =列数です。

問題は、グリッド内で最も接続されたチェーンを見つけることです。この場合、セル（0,0）からセル（2）への1-1-1-1-1です。 、2）。ここで

は、これまでの私のコードです：

def find(x, y): 
    #uses recursive fill 
    if x < 0 or y < 0 or matrix[x][y] == -1 or matrix[x][y] == 0 or x>n or y>m: 
     return 0 
    else: 
     return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 

matrix = [[0 for a in range(n)] for b in range(m)] 

#captures data and puts it in a matrix 
for i in range(n): 
    row = map(int, raw_input().strip().split()) 
    for j in range(m): 
     matrix[i][j] = row[j] 

sums = 0 
for i in range(n): 
    for k in range(m): 
     if matrix[i][k] == 1: 
      print matrix[i][k] 
      sums = max(find(i, k)) 

print sums 

今、私はこのプログラムを実行すると、私は、「ランタイムエラー」を取得していますが、私は理由を理解することはできません。私はfind関数で再帰的な記入をしています。セルはと等しい場合は、コードの残りの部分は、ちょうどfind機能をマトリックスにraw_input()からの値を格納し、入る1.

EDIT：

私はこのようになります長い繰り返しエラーを取得しています（短縮） ：

Traceback (most recent call last): 
    File "solution.py", line 27, in <module> 
    sums = max(find(i, k)) 
    File "solution.py", line 11, in find 
    return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 
    File "solution.py", line 11, in find 
    return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 
    File "solution.py", line 11, in find 
    return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 
    File "solution.py", line 11, in find 
    return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 
    File "solution.py", line 11, in find 
    return 1 + find(x+1, y) + find(x-1, y) + find(x, y+1) + find(x, y-1)+ find(x+1, y-1)+ find(x-1,y+1) + find(x+1, y+1) + find(x-1, y-1) 
    File "solution.py", line 11, in find 

また、この解決策はおそらく最良ではありません（私はPythonで初めてです）。だから提案はありがたいです。

Answer 1

matrix[x][y] == -1 or matrix[x][y] == 0の前にx>n or y>mをチェックする必要があります。それ以外の場合は、out of rangeエラーが発生する可能性があります。

また、あなたは何とかあなたの方法をマークするか、無限再帰で終わるでしょう。あなたの例では右→左→右→左...となり、常に1が見つかります。

Answer 2

は私が

1. はあなたが1を見つける右上隅
2. に開始するので、あなたは、無限再帰に実行していると思うので、今return 1 + find(x+1, y) + ...
3. 次回1を見ています最初のものに戻る
4. だから、return 1 + find(x+1, y) + find(x-1, y) 右上のコーナーの1 NER再び（x-1, y）
5. 後藤1

考えられる解決策：多分2で、位置 "使用" のマーク。