ARC#005 C - 器物損壊！高橋君 ( Search and destroy )

道への移動は距離0、壁への移動は距離2と考えて、幅優先探索。

# coding: utf-8
H,W = [int(x)+6 for x in raw_input().split()]
c = ["#"*W]*3+["###"+raw_input()+"###" for y in range(H-6)]+["#"*W]*3
D = [[9]*W for y in range(H)]   # 家からの壁の破壊回数
Q = [[],[],[]]                  # 壁の破壊回数i回の地点
for y in range(H):
    for x in range(W):
        if c[y][x]=="s":
            D[y][x] = 0
            Q[0] += [(x,y)]
for q in Q:
    while len(q)>0:
        x,y = q.pop()
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            tx,ty = x+dx,y+dy
            d = D[y][x]+1 if c[ty][tx]=="#" else D[y][x]
            if d<=2 and d<D[ty][tx]:
                D[ty][tx] = d
                Q[d] += [(tx,ty)]
for y in range(H):
    for x in range(W):
        if c[y][x]=="g":
            print "YES" if D[y][x]<=2 else "NO"