[At Coder] Résoudre les problèmes typiques de la recherche de priorité en profondeur (DFS)

Je veux être un professionnel compétitif, alors [Ce site (version AtCoder! Arimoto (Débutant))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2 -5-5warshall-floyd-% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) pour résoudre le problème d'AtCoder et La fondation est solidifiée. La solution cette fois-ci est AtCoder A-depth priority search. Il s'agit d'un problème typique de recherche de priorité de profondeur (DFS), qui est un type de recherche complète.

problème

Dans une ville rectangulaire au nord, au sud, à l'est et à l'ouest, la question est de savoir si vous pouvez accéder à la poissonnerie de votre maison par la route sans passer par un mur en chemin.

Solution

Cette fois, nous allons le résoudre en empilant sans utiliser de récurrence. [Wikipédia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4 La page de recherche de priorité de profondeur% A2) permet de comprendre facilement les grandes lignes de l'algorithme.

Comme point à résoudre,

■ Partie générale DFS

--Créez une pile et placez des nœuds non visités

■ Pièce spécifique à ce problème

――Je ne connais pas la position de départ, alors vérifiez-la d'abord (= mettez-la dans la pile)

Quel endroit, comme. Vous trouverez ci-dessous le code python.

from collections import deque
 
H,W = map(int, input().split())
C = [input() for _ in range(H)]
 
#Vérifiez la position de s à l'avance
for n1,c_w in enumerate(C):
    for n2,c in enumerate(c_w):
        if c == "s":
            s_h = n1
            s_w = n2
            
stack = deque([[s_h, s_w]])  #Créer une pile contenant uniquement la position de départ
 
visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1
 
def dfs(town, visited_list, stack):
    while len(stack) > 0:
        h, w = stack.pop()
        if town[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
                visited_list[new_h][new_w] = 1
                stack.append([new_h, new_w])
    
    return "No"
 
print(dfs(C, visited_list, stack))

Recommended Posts

[At Coder] Résoudre les problèmes typiques de la recherche de priorité en profondeur (DFS)
[Chez Coder] Résoudre le problème de la dichotomie
[At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
Problème de fractionnement typique de la combinaison de problèmes
Résolvez A ~ D du codeur yuki 247 avec python
[Python] DFS (recherche de priorité en profondeur) ATC001A
[Python] DFS (recherche de priorité en profondeur) ABC157D
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Algorithme en Python (recherche de priorité en profondeur, dfs)
Écrire une recherche de priorité en profondeur en Python
J'ai essayé de résoudre la recherche de priorité de profondeur (DFS) d'AtCoder en Python (résultat: TLE ...)
Essayez de résoudre un problème défini de mathématiques au lycée avec Python
Vous voulez résoudre un problème de classification simple?
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python