[PYTHON] [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.

• En passant, si ce problème est résolu par la recherche de priorité de largeur (BFS), il devient le problème de route le plus court sans poids latéraux.

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

• Marquer le nœud visité comme visité

• Obligatoire lorsqu'il y a une route fermée

• Retirer un par un de la pile et traiter

• Parce que c'est une pile, "dernier entré, premier sorti". Cela réalise DFS.

■ 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)

• Il existe quatre types de nœuds connectés au nœud parent (x, y): (x-1, y), (x + 1, y), (x, y-1), (x, y + 1).

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))