迷路はグラフ探索と捉えるのが有効
サンプルコード
# pythonだとデフォルトの再帰処理回数の上限に引っかかってしまうので、それを変更
import sys
sys.setrecursionlimit(1000000)
# 再帰関数DFSの定義
def dfs(x, y):
#マーク
d[x][y] = 1
# 移動4方向をループ
for i in range(4):
X = x + dx[i]
X = y + dy[i]
# X と Y が街の範囲内か、行ったことがないか、塀ではないかを判定
if 0 <= X and X < n and 0 <= Y and Y < m and d[X][Y] == 0 and c[X][Y] != "#":
dfs(X, Y)
# 入力
n, m = map(int, input().split())
c = [list(input()) for i in range(n)]
# 到達したかどうか（0は未到達、1は到達済み）
d = [[0] * m for i in range(n)]
# 移動する4方向
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# スタート地点から dfs を始める
for i in range(n):
for j in range(m):
if c[i][j] == "s":
dfs(i, j)
# ゴール地点に到達したかどうか
for i in range(n):
for j in range(m):
if c[i][j] == "g" and d[i][j]:
print("Yes")
exit()
print("No")