Submission #421369

---

Source Code Expand

mx = [1, 0, -1, 0]
my = [0, 1, 0, -1]
ngXRange = lambda x: not (0 <= x < W)
ngYRange = lambda y: not (0 <= y < H)
 
def dfs(now, goal):
    visited[now[0]][now[1]] = True
    if now == goal:
        return True
    for i in range(4):
        ny = now[0] + my[i]
        nx = now[1] + mx[i]
        if ngXRange(nx) or ngYRange(ny) or visited[ny][nx] or table[ny][nx] == "#":
            continue
        dfs([ny, nx], goal)
        if [ny, nx] == goal:
            return True
    return False
 
 
H, W = map(int, input().split())
table = [list(input()) for _ in range(H)]
visited = [[False for _ in range(W)]for _ in range(H)]
start = []
goal = []
for i in range(H):
    for j in range(W):
        if table[i][j] == "s":
            start = [i, j]           
        if table[i][j] == "g":
            goal = [i, j]
print("Yes" if dfs(start, goal) else "No")

Submission Info

Judge Result