Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
import copy

#N=int(input())
H,W=map(int,input().split(" "))
ch,cw=map(int,input().split(" "))
dh,dw=map(int,input().split(" "))


s=[]
for i in range(H):
  t=list(input())
  s.append(t)

min_warp=100000
total_warp=0

def ido(a, b, w, c):
  S = copy.copy(c)
  if a==dh-1 and b==dw-1:
    #print("goal")
    global min_warp
    if min_warp > w:
      min_warp = w
      #print("w",w)
  else:      
    if a+1 < H and S[a+1][b] == ".":
      S[a+1][b]='x'
      ido(a+1, b, w, S)

    if b+1 < W and S[a][b+1] == ".":
      S[a][b+1]='x'
      #print("bbbbb")
      ido(a, b+1, w, S)

    if a-1 >= 0 and S[a-1][b] == ".":
      S[a-1][b]='x'
      ido(a-1, b, w, S)

    if b-1 >= 0 and S[a][b-1] == ".":
      S[a][b-1]='x'
      ido(a, b-1, w, S)

    for i in range(-2,3):
      for j in range(-2,3):
        if a+i < H and a+i >= 0 and b+j < W and b+j >=0 and S[a+i][b+j] == ".":
          #print("i",i,"j",j)
          S[a+i][b+j]='x'
          w=w+1
          #print("aaaa")
          ido(a+i, b+j, w, S)

s[ch-1][cw-1]='x'
ido(ch-1, cw-1, total_warp, s)

if min_warp == 100000:
  min_warp = -1
print(min_warp)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)

print (res_S[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        if [nowh,noww]==[Dh,Dw]:
            print(s2[nowh][noww])
            exit()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, nowh+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

from collections import deque


H, W = [int(x) for x in input().split()]
Ch, Cw = [int(x) - 1 for x in input().split()]
Dh, Dw = [int(x) - 1 for x in input().split()]

warp_list = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
             (-1, -2), (-1, -1), (-1, 1), (-1, 2),
             (0, -2), (0, 2),
             (1, -2), (1, -1), (1, 1), (1, 2),
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([-1] * W)

queue = deque()
warp_queue = deque()

queue.appendleft((Ch, Cw, 0))

answer = -1
while queue:
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] == -1:
            return True
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.pop()

    if now_h == Dh and now_w == Dw:

        if answer == -1:
            answer = use_magic

        elif answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        warp_count[now_h][now_w] = use_magic
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        warp_count[now_h - 1][now_w] = use_magic
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        warp_count[now_h][now_w + 1] = use_magic
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        warp_count[now_h][now_w - 1] = use_magic
        do_warp = False

    if do_warp:
        warp_queue.appendleft((now_h, now_w))

    if not queue:
        while warp_queue:
            warp_h, warp_w, use_magic = warp_queue.pop()

            for y, x in warp_list:
                warp_h += y
                warp_w += x

                if maze_check(warp_h, warp_w, use_magic+1):
                    queue.append((warp_h, warp_w, use_magic+1))
                    warp_count[warp_h][warp_w] = use_magic + 1

print(answer)

Submission status: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(2000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
            break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI_()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch, cw))
    c[(ch, cw)] = 0
    nq = deque()
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            nq.append((mh, mw))
            for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for i in range(-2, 3):
                i += nh
                if 0 <= i < h:
                    si = s[i]
                    for j in range(-2, 3):
                        j += nw
                        if 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                            c[(i, j)] = now + 1
                            q.append((i, j))
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(h+2) for _ in range(w+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.popleft()

    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append([y+i,x+j])
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, nowh+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])

    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, nowh+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.append([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[]
ch-=1
cw-=1
dh-=1
dw-=1

for i in range(h):
    s.append(input())

d=[[10**10 for i in range(w)] for j in range(h)]
d=list(d)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1, 0, 0,0,0,0, 1, 1,1,1,1, 2, 2,2,2,2]
ddy=[-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
ans=[]
d[ch][cw]=0
que=deque([[ch,cw]])
while que:
    p=que.popleft()
    for i in range(4):
        if i<=3:
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]           
            if nx>=0 and ny>=0 and nx<h and ny<w and s[ny][nx]!="#" and d[ny][nx]>d[p[1]][p[0]]:
                d[ny][nx]=d[p[1]][p[0]]
                que.appendleft([nx,ny])
    for i in range(len(ddx)):
        nx=p[0]+ddx[i]
        ny=p[1]+ddy[i]
        if nx>=0 and ny>=0 and nx<h and ny<w and s[ny][nx]!="#" and d[ny][nx]>d[p[1]][p[0]]+1:
            d[ny][nx]=d[p[1]][p[0]]+1
            que.append([nx,ny])

if d[dh][dw]==10**10:
    print(-1)
else:
    print(d[dh][dw])

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  if a[0]-1>=0 and (S[a[0]-1][a[1]]==-1 or (S[a[0]-1][a[1]]!="#" and S[a[0]-1][a[1]]>S[a[0]][a[1]])):
    S[a[0]-1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]-1,a[1]))
  if a[0]+1<H and (S[a[0]+1][a[1]]==-1 or (S[a[0]+1][a[1]]!="#" and S[a[0]+1][a[1]]>S[a[0]][a[1]])):
    S[a[0]+1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]+1,a[1]))
  if a[1]-1>=0 and (S[a[0]][a[1]-1]==-1 or (S[a[0]][a[1]-1]!="#" and S[a[0]][a[1]-1]>S[a[0]][a[1]])):
    S[a[0]][a[1]-1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]-1))
  if a[1]+1<W and (S[a[0]][a[1]+1]==-1 or (S[a[0]][a[1]+1]!="#" and S[a[0]][a[1]+1]>S[a[0]][a[1]])):
    S[a[0]][a[1]+1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]+1))
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or S[a[0]-2+i][a[1]-2+j]>=S[a[0]][a[1]]+1):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        i, j = dx_dy[i][0], dx_dy[i][1]
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

A = 10**18
B = 10**9

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

d[(ch-1) * w + (cw-1)] = 0

T = ((-1,0), (1,0), (0,1), (0,-1))

q = [(ch-1)*A + (cw-1)*B + 0]
use = [0] * (h * w)

for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    tmp = curh * w * curw
    if d[tmp] < cnt or use[tmp]: continue
    d[tmp] = cnt
    use[tmp] = 1

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            use[nh * w + nw] = 0
            q.append(nh*A + nw*B + cnt)
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt + 1
            use[nh * w + nw]
            q.append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        i, j = dx_dy[i][0], dx_dy[i][1]
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = list(map(int, input().strip().split()))
ch, cw = list(map(int, input().strip().split()))
dh, dw = list(map(int, input().strip().split()))    
ch -= 1    
cw -= 1    
dh -= 1    
dw -= 1    
    
s = []    
for i in range(h):    
    row = input().strip()    
    s.append(row)    
    
dirs = ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1))    
gfp = set()    
q = deque()    
q.appendleft((cw, ch))    
done = False      
def walk(sx, sy, cnt):     
    fp = set()    
    global q      
    while q:                             
        bx, by = q.pop()       
        for dx, dy in dirs:    
            x, y = (bx + dx, by + dy)    
            if (x,y) in fp:    
                continue    
            fp.add((x, y))    
            if x < 0 or w <= x or y < 0 or h <= y:                     
                continue    
            if s[y][x] == '#':       
                continue           
            if (x, y) == (dw, dh):    
                return cnt    
            if 0 <= x < w and 0 <= y < h and s[y][x] == '.':    
                q.appendleft((x, y))    
    global gfp    
    gfp |= fp     
    for bx, by in fp:    
        for dx in range(-2, 3):        
            for dy in range(-2, 3):    
                x, y = (bx + dx, by + dy)    
                if 0 <= x < w and 0 <= y < h and s[y][x] == '.' and (x, y) not in gfp:    
                    q.appendleft((x,y))    
                    res = walk(x, y, cnt +1)    
                    if res > 0:    
                        return res    
    return -1    
print(walk(cw, ch, 0))

Submission status: Runtime Error

Solution code:
import collections

def bfs(now, goal, D, next_, seen, rank):
    for x in D[now]:
        if x in seen:
            continue
        if x == goal:
            return True
        else:
            next_.append((x,rank))
            seen.append(x)    


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
S = [[x for x in input()] for _ in range(h)]
A = [i for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue
        if i > 0:
            if S[i][j] == '.' and S[i-1][j] == '.':
                A[w*i+j] = A[w*(i-1)+j]
        if j > 0:
            if S[i][j] == '.' and S[i][j-1] == '.':
                A[w*i+j] = A[w*i+(j-1)]
#移動Aによる連結成分をノードとして移動Bで連結グラフを作成
B = collections.defaultdict(lambda:set())
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue
        for k in range(5):
            for l in range(3):
                if i+k-2 >= 0 and i+k-2 < h and j+l-2 >= 0:
                    if S[i][j] == '.' and S[i+k-2][j+l-2] == '.': #連結可能条件
                        if A[w*i+j] != A[w*(i+k-2)+(j+l-2)]:
                            B[A[w*i+j]].add(A[w*(i+k-2)+(j+l-2)])
                            B[A[w*(i+k-5)+(j+l-2)]].add(A[w*i+j])
                

if A[ch*w+cw] == A[dh*w+dw]: #Aで連結している
    ans = 0
else:
    next_ = [(A[ch*w+cw],0)]
    goal = A[dh*w+dw]
    seen = [A[ch*w+cw]]
    ans = 1
    while (True):
        if len(next_) == 0: #Bで連結してない
            ans = -1
            break
        now = next_[0][0]
        rank = next_[0][1] + 1
        next_.pop(0)
        if bfs(now, goal, B, next_, seen, rank): #Bで連結しているなら
            ans = rank
            break
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 0

while 1:
    while stack1:
        sh, sw = stack1.pop()
        stack2.append((sh, sw))
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                if nh == Dh and nw == Dw:
                    print(answer)
                    exit()
                grid[nh][nw] = 1
                stack1.append((nh, nw))
    answer += 1

    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                    if nh == Dh and nw == Dw:
                        print(answer)
                        exit()
                    grid[nh][nw] = 1
                    stack1.append((nh, nw))
    if !stack1:
        print(-1)
        exit()

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([ch-1, cw-1])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        i, j = k[0], k[1]
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([ch-1, cw-1])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        i, j = k[0], k-1 
        if 0 <= x+i < h and 0 <= y < w:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([ch-1, cw-1])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for i, j in dx_dy:
        if 0 <= x+i < h and 0 <= y < w:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == "."::
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])