・ Après avoir étudié Python, j'ai fait beaucoup de programmation compétitive ces derniers temps. Lors de la résolution des questions précédentes, je suis tombé sur la recherche de priorité en profondeur, j'ai donc résumé la solution. Le problème contesté est la recherche de priorité en profondeur pour le problème A dans le concours typique 001. https://atcoder.jp/contests/atc001/tasks/dfs_a
class Dfs():
def dfs(self, h, w, maze, init):
search_stack = [init] #Stocker les coordonnées initiales dans la pile de recherche
fin = [] #Définir la pile de complétion
while search_stack:
latest = search_stack.pop() #Extraire l'emplacement actuel de la pile de recherche
if maze[latest[0]][latest[1]] == "g": #Sortie Oui si votre emplacement actuel est Objectif
print("Yes")
exit()
else:
fin.append(latest) #Stocker les coordonnées recherchées dans la pile de complétion
candi = [(latest[0]-1, latest[1]), (latest[0]+1, latest[1]), (latest[0], latest[1]-1), (latest[0], latest[1]+1)] #Définir les candidats coordonnés
for (ny, nx) in candi:
if self.check_range(h, w, ny, nx): #Juger si les candidats coordonnateurs sont hors de portée
if self.check_wall(maze, ny, nx): #Déterminer si la coordonnée candidate est un mur
if not (ny, nx) in search_stack and not (ny, nx) in fin: #Déterminer si les coordonnées des candidats sont incluses dans la pile de recherche et la pile d'achèvement
search_stack.append((ny, nx)) #Stocker dans la pile de recherche
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")) #Rechercher un point de départ
d = Dfs()
d.dfs(h, w, maze, init)
break
except ValueError:
pass
Recommended Posts