Daily AtCoder # 26 avec Python

introduction

#25 Aujourd'hui, je vais résoudre le problème d'introduction de ce qu'on appelle DFS. J'ai fait référence à cet article.

DFS signifie Depth Priority Search. Un nom similaire est la recherche de priorité de largeur (BFS). Comme son nom l'indique, DFS donne l'impression d'aller du point du graphique actuel au point où vous pouvez aller. Explication détaillée

Le problème cette fois est qu'il ne spécifie pas où se trouve s. Alors, tout d'abord, recherchez l'emplacement de '. Lorsque vous trouvez les ', ajoutez les coordonnées de s à la pile (le type est collections.deque, pas la liste). La pile récupère le dernier élément que vous avez mis en premier. Ensuite, définissez la coordonnée de s dans la liste visitée sur 1. La signification de 1 est 0 ou 1 pour juger si elle a été recherchée. Cette liste_vitée est un ensemble de points recherchés. C'est le contenu de dfs.

Tant que la pile est vide.
Sortez le nouveau h, w (emplacement actuel) de la pile
Si h, w vaut «g», renvoie «Oui» et quitte.
Si h et w ne sont pas «g», procédez dans chaque direction. Ce problème se situe dans les directions [1, 0], [-1, 0], [0, 1], [0, -1].
Représente l'emplacement actuel + les coordonnées de la destination dans chaque direction.
Je ne pense pas que la destination soit hors de question, alors continuez.
Si la destination n'est pas '#' et le point non recherché, définissez la liste visitée [coordonnée] sur 1 et ajoutez de nouvelles coordonnées à la pile.

from collections import deque

h_in, w_in = map(int,input().split())
c = [input() for _ in range(h_in)]

for n1,c_w in enumerate(c):
    for n2,c1 in enumerate(c_w):
        if c1 == "s":
            s_h = n1
            s_w = n2

stack = deque([[s_h,s_w]])

visited_list = [[0]*w_in for _ in range(h_in)]
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_in or new_w < 0 or new_w >= w_in:
                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))

Résumé

Je suis passé par là quand le problème du graphe est sorti, mais je veux étudier dur et pouvoir le résoudre. Je vais continuer à me consacrer car cela ne prendra pas racine avec une seule question. à plus. bonne nuit