Submission #1685938

---

Source Code Expand

from collections import deque
def bfs(M,SX,SY,GX,GY,H,W):
    dxy4 = [1,0,-1,0,1]
    Q = deque()
    Q.append([SX,SY])
    while len(Q):
        X,Y = Q.popleft()
        T = M[Y][X] + 1
        for i in range(4):
            nx = X + dxy4[i]
            ny = Y + dxy4[i+1]
            if [nx,ny] == [GX,GY]:
                M[ny][nx] = T
                return T
            if 0<= nx < W and 0 <= ny < H and T < M[ny][nx]:
                M[ny][nx] = T
                Q.append([nx,ny])
    return -1

h,w = map(int,input().split())
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))
m = [list(input()) for i in range(h)]
m = [[ -1 if m[i][j] == '#'else 999999 for j in range(w)]for i in range(h)]
m[sy-1][sx-1]= 0
print(bfs(m,sx-1,sy-1,gx-1,gy-1,h,w))

Submission Info

Judge Result