如何使用递归在网格中查找连接的单元格？

Question

我做，给出了一个网格，如一个问题：

n =行数，m =列数。

问题是要在网格中找到最连接的“1”链......在这种情况下：它是从单元格（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函数。的代码的其余部分只存储从raw_input()值到一个矩阵，并进入find功能如果该细胞是等于1

编辑：

我得到一个长重复错误，看起来像这样（缩短） ：

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. 您在右上角
2. 开始你找到一个1，所以你return 1 + find(x+1, y) + ...
3. 现在你正在寻找下一个1正确的第一个
4. 所以你return 1 + find(x+1, y) + find(x-1, y)
5. 因此看在右上角的1 NER再次（x-1, y）
6. 转到1

可能的解决方法： “已使用” 的位置，可能与2马克。