蟒蛇深度优先搜索递归

Question

我试图使连接用递归岛蟒蛇DFS ...

程序工作正常，但是在某些情况下有其输出是不正确逻辑错误

例如

o o o 

o x x 

o o o the output is 1 which is correct. 

然而，在其他情况下

o x o 

o x o 

o o o the output is 2 which is incorrect. 

这里是我完整的代码，包括DFS在我看来，功能

row = int(input("Enter Row : ")) 
col = int(input("Enter Col : ")) 

# declare array baru namanya peta 
peta = [] 

# array 2 dimensi 
# Masukkin smua input ke array petas 
for i in range(0,row): 
    line = input() 
    peta.append(line) 


store = [] 
# declare array baru nama visited 
visited = [] 
for i in range(0,row): 
    visited.append([]) 

    # buat column di row i false smua 
    for j in range(0,col): 
     visited[i].append(False) 

def dfs(i,j): 
    visited[i][j] = True 
    a = row-1 
    b = col-1 
    #peta[i][j] = store[a][b] 
    for i in range(i,row): 
     for j in range(j,col): 
      if(visited[i][j] == True): 
       return 1 
      else: 
       if(peta[i][j] == 'x' and visited[i][j] == False):     
        #top left array 
        if(i == 0 or j == 0): 
         dfs(i+1,j+1) 
         dfs(i+1,j) 
         dfs(i,j+1)     

        #bottom left array 
        elif(i == a and j == 0): 
         dfs(i-1,j) 
         dfs(i-1,j+1) 
         dfs(i,j+1) 

        #top right array 
        elif(i == 0 and j == b): 
         dfs(i,j-1) 
         dfs(i+1,j-1) 
         dfs(i+1,j) 

        #bottom right array 
        elif(i == a and j == b): 
         dfs(i,j-1) 
         dfs(i-1,j-1) 
         dfs(i-1,j) 

        #west array 
        elif(i >= 1 and j == 0): 
         dfs(i-1,j) 
         dfs(i-1,j+1) 
         dfs(i+1,j) 
         dfs(i,j+1) 
         dfs(i+1,j+1) 

        #north array 
        elif(i==0 and j>=1): 
         dfs(i,j-1) 
         dfs(i+1,j-1) 
         dfs(i+1,j) 
         dfs(i,j+1) 
         dfs(i+1,j+1) 

        #east array 
        elif(i>=1 and j==b): 
         dfs(i-1,j) 
         dfs(i-1,j-1) 
         dfs(i,j-1) 
         dfs(i+1,j-1) 
         dfs(i+1,j) 

        #south array 
        elif(i==a and j>=1): 
         dfs(i,j-1) 
         dfs(i-1,j-1) 
         dfs(i-1,j) 
         dfs(i-1,j+1) 
         dfs(i,j+1) 

        #middle array 
        else: 
         dfs(i-1,j-1) 
         dfs(i-1,j) 
         dfs(i-1,j+1) 
         dfs(i,j-1) 
         dfs(i,j+1) 
         dfs(i+1,j-1) 
         dfs(i+1,j) 
         dfs(i+1,j+1) 

       else: 
        #peta[i][j] = 0 
        return 0 

numberofisland = 0 
for i in range(0,row): 
    for j in range(0,col): 
     if((peta[i][j] == 'x' and visited[i][j] == False)): 
      dfs(i,j) 
      numberofisland+=1 





print(numberofisland) 

，我的逻辑错误是我参观访问的节点两次，但是似乎在我的数组没有错误。你能否就我的错误在哪里提出一些建议？

非常感谢您的宝贵时间，欢呼声

编辑：我已经更新到完整的代码版本为社区请求（如何调用该函数，全局变量等）

Answer 1

有些事情在你的代码没有意义：

1）如果你想从dfs函数返回一个值，这个值应该有一些意义，应该使用它。如果您只为其副作用调用函数，那么只需return就没有价值。在这种情况下，它看起来像dfs函数的目的是更新visited数组，因此您不需要返回1或0或其他任何东西。

2）当您在图中进行深度优先搜索时，您从一个节点开始，并且递归访问其连接的节点。如果你在dfs函数中有一个for循环，它访问图表的大部分内容，忽略连接，那么你就没有做DFS。通常，您只需递归调用连接节点上的dfs函数。

3）现在你的函数看起来好像在返回调用之前总是返回1。

也采取了Python代码下面的良好做法注：

1）避免结构，如if expression == True:。请使用if expression:。而不是if expression == False，请使用if not expression。

2）避免在if和elif子句的条件表达式附近使用括号，因此不像C或Java那样需要使用括号。例如，而不是elif (a == b):使用elif a == b。

3）在函数的顶部添加一个docstring来描述函数的功能（请参阅下面的代码示例）。

从我所了解的情况来看，您需要每次调用dfs函数来访问所有连接的形成岛的x。您可以使用以下代码执行此操作：

def dfs(i,j): 
    ''' 
    This function starts from the square with coordinates (i,j). 

    The square (i,j) should be an 'x', and also unvisited. 

    This function will keep visiting all adjacent 'x' squares, using a 
    depth first traversal, and marking these squares as visited in the 
    @visited array. 

    The squares considered adjacent are the 8 surrounding squares: 
    (up, up-right, right, down-right, down, down-left, left, up-left). 
    ''' 

    # The range checks have been moved to the beginning of the function, after each call. 
    # This makes the code much shorter. 
    if i < 0 or j < 0 or i >= row or j >= col: 
     return 

    # If we reached a non-x square, or an already visited square, stop the recursion. 
    if peta[i][j] != 'x' or visited[i][j]: 
     # Notice that since we don't do something with the return value, 
     # there is no point in returning a value here. 
     return 

    # Mark this square as visited. 
    visited[i][j] = True 

    # Visit all adjacent squares (up to 8 squares). 
    # Don't worry about some index falling out of range, 
    # this will be checked right after the function call. 
    dfs(i-1,j-1) 
    dfs(i-1,j) 
    dfs(i-1,j+1) 
    dfs(i,j-1) 
    dfs(i,j+1) 
    dfs(i+1,j-1) 
    dfs(i+1,j) 
    dfs(i+1,j+1)