Il est efficace de considérer le labyrinthe comme une recherche graphique
Exemple de code
#En python, il reste bloqué dans la limite par défaut du nombre de traitements récursifs, alors changez-le
import sys
sys.setrecursionlimit(1000000)
#Définition de la fonction récursive DFS
def dfs(x, y):
#marque
d[x][y] = 1
#Boucle dans 4 directions
for i in range(4):
X = x + dx[i]
X = y + dy[i]
#Déterminez si X et Y sont dans la ville, n'ont jamais été ou ne sont pas un mur
if 0 <= X and X < n and 0 <= Y and Y < m and d[X][Y] == 0 and c[X][Y] != "#":
dfs(X, Y)
#contribution
n, m = map(int, input().split())
c = [list(input()) for i in range(n)]
#S'il a été atteint (0 n'est pas atteint, 1 est atteint)
d = [[0] * m for i in range(n)]
#4 directions pour se déplacer
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#Démarrer dfs à partir du point de départ
for i in range(n):
for j in range(m):
if c[i][j] == "s":
dfs(i, j)
#Si vous avez atteint le point objectif
for i in range(n):
for j in range(m):
if c[i][j] == "g" and d[i][j]:
print("Yes")
exit()
print("No")
Recommended Posts