Submission #423153

---

Source Code Expand

# -*- coding: utf-8 -*-
u"""
ATC001 A 深さ優先探索
"""

town = []

def main():
    u"""
    Main Function
    """
    H, W = map(int, raw_input().split())
    stack = []
    
    # 街の外側に塀をつけた状態にして読み込む 番兵法
    town.append(["#" for i in range(W+2)])
    for i in range(H):
        town.append(["#"] + list(raw_input()) + ["#"])
        for j, b in enumerate(town[-1]):
            if b == "s":
                stack.append([i+1, j])
                town[i+1][j] = "o"
    town.append(["#" for i in range(W+2)])

    while (len(stack)>0):
        i, j = stack.pop()
        
        if town[i+1][j] == ".":
            town[i+1][j] = "o"
            stack.append([i+1,j])
        elif town[i+1][j] == "g":
            print "Yes"
            return
        if town[i-1][j] == ".":
            town[i-1][j] = "o"
            stack.append([i-1,j])
        elif town[i-1][j] == "g":
            print "Yes"
            return
        if town[i][j+1] == ".":
            town[i][j+1] = "o"
            stack.append([i,j+1])
        elif town[i][j+1] == "g":
            print "Yes"
            return
        if town[i][j-1] == ".":
            town[i][j-1] = "o"
            stack.append([i,j-1])
        elif town[i][j-1] == "g":
            print "Yes"
            return
            
    print "No"
    
def show(arr):
    for i in range(len(arr)):
        print " ".join(arr[i])

    print ""
	
if __name__=="__main__":
    main()

Submission Info

Judge Result