蟒蛇深度優先搜索遞歸

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)