recherche python profondeur d'abord récursion

Question

je suis en train de faire un DSF python connexion île avec récursion ...

le programme fonctionne très bien, mais sur certains cas, il y a une erreur logique dans laquelle la sortie est incorrecte

Par exemple

o o o 

o x x 

o o o the output is 1 which is correct. 

Cependant, sur d'autres cas

o x o 

o x o 

o o o the output is 2 which is incorrect. 

Voici mon code complet qui comprend DSF fonction

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) 

à mon avis, mon erreur logique est je visite deux fois le noeud visité, mais il semble aucune erreur dans mes tableaux. Pouvez-vous donner une idée de l'endroit où se trouve mon erreur?

Merci beaucoup pour votre temps, acclamations

edit: je l'ai mis à jour dans la version complète du code en tant que communauté demandé (comment appeler la fonction, variable globale, etc.)

Answer 1

Certaines choses dans votre code n'a pas de sens:

1) Si vous souhaitez renvoyer une valeur à partir de la fonction dfs, cette valeur doit avoir une signification et doit être utilisée. Si vous appelez seulement une fonction pour ses effets secondaires, alors vous pouvez juste return sans valeur. Dans ce cas, il me semble que comme le but de la fonction dfs est de mettre à jour le tableau visited, de sorte que vous n'avez pas besoin de retourner 1 ou quoi que ce soit ou 0.

2) Lorsque vous effectuez une recherche en profondeur d'abord dans un graphique, vous commencez à un noeud, et vous visitez récursive ses noeuds connectés. Si vous disposez d'une boucle forcée à l'intérieur de la fonction dfs qui visite une grande partie du graphique, en ignorant les connexions, vous ne faites pas de DFS. Généralement, il suffit d'appeler récursivement la fonction dfs sur les nœuds connectés.

3) La façon dont votre fonction semble en ce moment, il semble que ce sera toujours revenir 1 avant de faire des appels récursifs.

Veuillez également prendre note des bonnes pratiques suivantes pour le code Python:

1) Évitez les constructions comme if expression == True:. Au lieu de cela, utilisez if expression:. Aussi, au lieu de if expression == False, utilisez if not expression.

2) Évitez d'utiliser des parenthèses autour de l'expression conditionnelle dans les clauses if et elif, il n'est pas nécessaire, contrairement à C ou Java. Par exemple, au lieu de elif (a == b):, utilisez elif a == b.

3) Ajouter un docstring en haut d'une fonction, pour décrire la fonction (voir mon code ci-dessous pour un exemple).

D'après ce que je comprends, vous voulez pour chaque appel de la fonction dfs pour visiter tous les xs connectés qui forment une île.Vous pouvez le faire avec le code suivant:

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)