Täglicher AtCoder # 26 mit Python

Einführung

Letztes Mal 25. Tag

#25 Heute werde ich das Einführungsproblem der sogenannten DFS lösen. Ich habe auf [diesen Artikel] verwiesen (https://qiita.com/gh_takumi/items/79537ade8d2539d89bd2).

DFS steht für Depth Priority Search. Ein ähnlicher Name ist Width Priority Search (BFS). Wie der Name schon sagt, möchte DFS vom Punkt im aktuellen Diagramm zum Punkt gehen, an dem Sie gehen können. Detaillierte Erklärung

Das Problem ist diesmal, dass nicht angegeben wird, wo sich s befindet. Suchen Sie also zuerst nach dem Standort von '. Wenn Sie das 'finden, fügen Sie die Koordinaten von s zum Stapel hinzu (Typ ist collection.deque, nicht list). Der Stapel ruft das letzte Element ab, das Sie zuerst eingegeben haben. Setzen Sie als nächstes die Koordinate von s in visit_list auf 1. Die Bedeutung von 1 ist 0 oder 1, um zu beurteilen, ob gesucht wurde. Diese besuchte Liste besteht aus einer Reihe von gesuchten Punkten. Dies ist der Inhalt von dfs.

1. Während, bis der Stapel leer ist.
2. Nehmen Sie das neue h, w (aktuelle Position) aus dem Stapel
3. Wenn h, w 'g' ist, geben Sie 'Yes' zurück und beenden Sie das Programm.
4. Wenn h und w nicht 'g' sind, fahren Sie in jede Richtung fort. Dieses Problem liegt in den Richtungen [1, 0], [-1, 0], [0, 1], [0, -1].
5. Repräsentiert den aktuellen Standort + die Koordinaten des Ziels in jeder Richtung.
6. Ich glaube nicht, dass das Ziel nicht in Frage kommt, also fahren Sie fort.
7. Wenn das Ziel nicht '#' und nicht gesuchter Punkt ist, setzen Sie visit_list [Koordinate] auf 1 und fügen Sie dem Stapel neue Koordinaten hinzu.

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

Zusammenfassung

Ich bin durchgekommen, als das Problem des Graphen herauskam, aber ich möchte hart studieren und es lösen können. Ich werde mich weiterhin widmen, weil es nicht mit nur einer Frage Wurzeln schlagen wird. wir sehen uns. Gute Nacht