Submission #2554721

---

Source Code Expand

# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(10000000)
def inpl(): return map(int, input().split())

H, W = inpl()
searched = [[True]*(W+2)]
for h in range(H):
    tmp = "#" + input() + "#"
    if "s" in tmp:
        sh, sw = h+1, tmp.index("s")
    if "g" in tmp:
        gh, gw = h+1, tmp.index("g")

    searched.append([t == "#" for t in tmp])
searched.append([True]*(W+2))

direct = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def dfs(h, w):
    if (h, w) == (gh, gw):
        print("Yes")
        exit()

    for i in range(4):
        dh, dw = direct[i]
        if not searched[h+dh][w+dw]:
            searched[h+dh][w+dw] = True
            dfs(h+dh, w+dw)
    return None


searched[sh][sw] = True
dfs(sh, sw)
print("No")

Submission Info

Judge Result