Submission #420839

---

Source Code Expand

# -*- coding: utf-8 -*-
H, W = map(int, raw_input().split())
blocks = []
start = (-1,-1)
goal = (-1,-1)
for i in range(H):
    street = raw_input()
    if 's' in street:
        start = (i,street.index('s'))
    if 'g' in street:
        goal = (i,street.index('g'))
    blocks.append(street)
visited = {}
stack = []
stack.append(start)
visited[start]=1
flag = False
while stack:
    cur = stack.pop()
    if cur[0]+1<H and (cur[0]+1,cur[1]) not in visited:
        if blocks[cur[0]+1][cur[1]] == '.':
            stack.append((cur[0]+1,cur[1]))
            visited[(cur[0]+1,cur[1])]=1
        if blocks[cur[0]+1][cur[1]] == 'g':
            flag = True
            break
    if cur[0]-1>=0 and (cur[0]-1,cur[1]) not in visited:
        if blocks[cur[0]-1][cur[1]] == '.':
            stack.append((cur[0]-1,cur[1]))
            visited[(cur[0]-1,cur[1])]=1
        if blocks[cur[0]-1][cur[1]] == 'g':
            flag = True
            break
    if cur[1]-1>=0 and (cur[0],cur[1]-1) not in visited:
        if blocks[cur[0]][cur[1]-1] == '.':
            stack.append((cur[0],cur[1]-1))
            visited[(cur[0],cur[1]-1)]=1
        if blocks[cur[0]][cur[1]-1] == 'g':
            flag = True
            break
    if cur[1]+1<W and (cur[0],cur[1]+1) not in visited:
        if blocks[cur[0]][cur[1]+1] == '.':
            stack.append((cur[0],cur[1]+1))
            visited[(cur[0],cur[1]+1)]=1
        if blocks[cur[0]][cur[1]+1] == 'g':
            flag = True
            break
if flag:
    print "Yes"
else:
    print "No"

Submission Info

Judge Result