It is effective to regard the maze as a graph search.
Sample code
#In python, it gets stuck in the default recursive processing limit, so change it
import sys
sys.setrecursionlimit(1000000)
#Definition of recursive function DFS
def dfs(x, y):
#mark
d[x][y] = 1
#Loop in 4 directions
for i in range(4):
X = x + dx[i]
X = y + dy[i]
#Determine if X and Y are within the city, have never been, or are not a fence
if 0 <= X and X < n and 0 <= Y and Y < m and d[X][Y] == 0 and c[X][Y] != "#":
dfs(X, Y)
#input
n, m = map(int, input().split())
c = [list(input()) for i in range(n)]
#Whether it has been reached (0 is not reached, 1 is reached)
d = [[0] * m for i in range(n)]
#4 directions to move
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#Start dfs from the starting point
for i in range(n):
for j in range(m):
if c[i][j] == "s":
dfs(i, j)
#Whether you have reached the goal point
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