[PYTHON] [At Coder] Lösen Sie typische Probleme der Tiefenprioritätssuche (DFS).

Ich möchte ein wettbewerbsfähiger Profi sein, also [Diese Seite (AtCoder-Version! Arimoto (Anfänger))](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), um das AtCoder-Problem zu lösen und den Algorithmus zu lösen Das Fundament ist verfestigt. Dieses Mal werden wir [AtCoders A-Tiefen-Prioritätssuche] lösen (https://atcoder.jp/contests/atc001/tasks/dfs_a). Dies ist ein typisches Problem der Tiefenprioritätssuche (DFS), bei der es sich um eine Art vollständige Suche handelt.

Problem

In einer rechteckigen Stadt im Norden, Süden, Osten und Westen stellt sich die Frage, ob Sie den Fischladen von Ihrem Haus aus über die Straße erreichen können, ohne unterwegs durch eine Mauer zu gehen.

• Wenn dieses Problem durch die Breitenprioritätssuche (BFS) gelöst wird, wird es übrigens zum kürzesten Routenproblem ohne Seitengewichte.

Lösung

Dieses Mal werden wir es lösen, indem wir ohne Wiederholung stapeln. [Wikipedia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4 Die Seite% A2) Tiefenprioritätssuche gibt einen Überblick über den Algorithmus.

Als ein Punkt zu lösen,

■ Allgemeiner Teil der DFS

--Erstellen Sie einen Stapel und fügen Sie nicht besuchte Knoten ein

• Markieren Sie den besuchten Knoten als besucht

• Erforderlich, wenn eine Straße gesperrt ist --Eine nacheinander vom Stapel entfernen und verarbeiten
• Da es sich um einen Stapel handelt, "last in, first out". Dies realisiert DFS.

■ Teil für dieses Problem

――Ich kenne die Startposition nicht, also überprüfe sie zuerst (= lege sie in den Stapel)

• Es gibt vier Arten von Knoten, die mit dem übergeordneten Knoten (x, y) verbunden sind: (x-1, y), (x + 1, y), (x, y-1), (x, y + 1).

Was für ein Ort wie. Unten ist der Python-Code.

from collections import deque
 
H,W = map(int, input().split())
C = [input() for _ in range(H)]
 
#Überprüfen Sie die Position von s im Voraus
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]])  #Erstellen Sie einen Stapel, der nur die Startposition enthält
 
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))