・ Nachdem ich Python studiert habe, habe ich in letzter Zeit viel wettbewerbsfähiges Programmieren gemacht. Bei der Lösung der vergangenen Fragen bin ich auf die Suche nach Tiefenprioritäten gestoßen und habe die Lösung zusammengefasst. Das herausgeforderte Problem war die Suche mit Tiefenpriorität nach Problem A in Typical Contest 001. https://atcoder.jp/contests/atc001/tasks/dfs_a
class Dfs():
def dfs(self, h, w, maze, init):
search_stack = [init] #Speichern Sie die Anfangskoordinaten im Suchstapel
fin = [] #Abschlussstapel definieren
while search_stack:
latest = search_stack.pop() #Extrahieren Sie den aktuellen Speicherort aus dem Suchstapel
if maze[latest[0]][latest[1]] == "g": #Ausgabe Ja, wenn Ihr aktueller Standort Ziel ist
print("Yes")
exit()
else:
fin.append(latest) #Speichern Sie die gesuchten Koordinaten im Fertigstellungsstapel
candi = [(latest[0]-1, latest[1]), (latest[0]+1, latest[1]), (latest[0], latest[1]-1), (latest[0], latest[1]+1)] #Koordinatenkandidaten definieren
for (ny, nx) in candi:
if self.check_range(h, w, ny, nx): #Beurteilung, ob Koordinatenkandidaten außerhalb des Bereichs liegen
if self.check_wall(maze, ny, nx): #Bestimmen Sie, ob der Koordinatenkandidat eine Wand ist
if not (ny, nx) in search_stack and not (ny, nx) in fin: #Bestimmen Sie, ob Koordinatenkandidaten im Suchstapel und im Abschlussstapel enthalten sind
search_stack.append((ny, nx)) #Im Suchstapel speichern
continue
print("No")
def check_range(self, h, w, y, x):
if x > w-1 or x < 0:
return False
elif y > h-1 or y < 0:
return False
else:
return True
def check_wall(self, maze, y, x):
if maze[y][x] == "#":
return False
else:
return True
if __name__ == "__main__":
h,w = map(int,input().split())
maze = [list(input()) for i in range(h)]
for y, row in enumerate(maze):
try:
init = (y, row.index("s")) #Suchen Sie nach einem Ausgangspunkt
d = Dfs()
d.dfs(h, w, maze, init)
break
except ValueError:
pass
Recommended Posts