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 sys
import pprint
import time
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [[-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]]

def solve(s_pos, d):
    queue = []
    queue.append(s_pos)
    dist[s_pos[0]][s_pos[1]] = d

    candidates = []
    while len(queue) > 0:
        y, x = queue.pop(0)
        candidates.append([y,x])
        for p, q in move:
            vh = y + p
            vw = x + q
            if 0 <= vh < h and 0 <= vw < w:
                if C[vh][vw] != "#" and (dist[vh][vw] == -1 or d < dist[vh][vw]):
                    dist[vh][vw] = dist[y][x]
                    queue.append([vh,vw])
    while len(candidates) > 0:
        y2, x2 = candidates.pop(0)
        for r, s in magic:
            vh2 = y2 + r
            vw2 = x2 + s
            if 0 <= vh2 < h and 0 <= vw2 < w:
                if C[vh2][vw2] != "#" and (dist[vh2][vw2] == -1 or d+1 < dist[vh2][vw2]):
                    solve([vh2,vw2], d+1)

solve([sh,sw], 0)
print(dist[gh][gw])

Submission status: Runtime Error

Solution code:
import sys
import pprint
import time
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [[-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]]

def solve(s_pos, d):
    queue = []
    queue.append(s_pos)
    dist[s_pos[0]][s_pos[1]] = d

    candidates = []
    while len(queue) > 0:
        y, x = queue.pop(0)
        candidates.append([y,x])
        for p, q in move:
            vh = y + p
            vw = x + q
            if 0 <= vh < h and 0 <= vw < w:
                if C[vh][vw] != "#" and dist[vh][vw] == -1:
                    dist[vh][vw] = dist[y][x]
                    queue.append([vh,vw])
    while len(candidates) > 0:
        y2, x2 = candidates.pop(0)
        for r, s in magic:
            vh2 = y2 + r
            vw2 = x2 + s
            if 0 <= vh2 < h and 0 <= vw2 < w:
                if C[vh2][vw2] != "#" and dist[vh2][vw2] == -1:
                    solve([vh2,vw2], d+1)

solve([sh,sw], 0)
print(dist[gh][gw])

Submission status: Runtime Error

Solution code:
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw - 1, Ch - 1))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny][nx] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny][nx] == -1 or costmap[y][x] < costmap[ny][nx]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny][nx] = costmap[y][x]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny][nx] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny][nx] == -1 or costmap[y][x] + 1 < costmap[ny][nx]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny][nx] = costmap[y][x] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dh - 1][Dw - 1])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappopfrom numba import njit
from numba import jit

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

@jit
def main():

    inf = 10**7
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))

    while q:
        cnt = 0
        cost, px, py = heappop(q)
        if dp[px][py] < cost:
            continue
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[inf]*w for _ in range(h)]
main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappopfrom numba import njit
from numba import jit

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

@jit
def main():

    inf = 10**7
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))

    while q:
        cnt = 0
        cost, px, py = heappop(q)
        if dp[px][py] < cost:
            continue
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])


main()
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[inf]*w for _ in range(h)]

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappopfrom numba import njit
from numba import jit

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

@jit
def main():

    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))

    while q:
        cnt = 0
        cost, px, py = heappop(q)
        if dp[px][py] < cost:
            continue
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])


main()
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for _ in range(h)]

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
import heapq as hp
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def is_valid(i, j):
        if 0 <= i < h and 0 <= j < w and ar[i][j] == 1:
            return True
        return False

    ar=[]
    for _ in range(h):
        ar.append([1 if i=="." else 0 for i in input() ])

    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    magic = [(0, 2), (2, 0), (0, -2), (-2, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (1, 2), (1, -2), (-1, 2), (-1, -2),
             (2, 1), (2, -1), (-2, 1), (-2, -1), (2, 2), (2, -2), (-2, 2), (-2, -2)]

    queue=[(0,ch-1,cw-1)]
    hp.heapify(queue)
    inf=flost("inf")
    di=[[inf]*(w+1) for _ in range(h+1) ]
    di[ch-1][cw-1]=0
    while queue:
        d,a,b=hp.heappop(queue)
        ar[a][b]=0
        if a==dh-1 and b==dw-1:
            print(di[a][b])
            exit()
        for i in move:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[x][y]=min(di[x][y],d)
                hp.heappush(queue, (di[x][y], x, y))


        for i in magic:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[x][ y] = min(di[x][ y], d+1)
                hp.heappush(queue, (di[x][ y], x, y))

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






solve()

Submission status: Runtime Error

Solution code:
import sys
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
sh-=1
sw-=1
gh-=1
gw-=1

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

def solve(s_pos):
    queue = []
    queue.append(s_pos)
    dist[s_pos[0]][s_pos[1]] = 0
    
    candidates = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        candidates.append([x,y])
        if x == gh and y == gw:
            return
        for i in range(4):
            v1 = x + dy_dx[i][1]
            v2 = y + dy_dx[i][0]
            if 0 <= v1 < h and 0 <= v2 < w:
                if C[v1][v2] != "#" and dist[v1][v2] == -1:
                    dist[v1][v2] = dist[x][y]
                    queue.append([y,x])
        if len(queue) == 0:
            while len(candidates) > 0:
                x2, y2 = candidates.pop()
                for i in range(-2,3):
                    if i == 0:
                        continue
                    for j in range(-2,3):
                        if j == 0:
                            continue
                        v1 = x + j
                        v2 = y + i
                        if 0 <= v1 < h and 0 <= v2 < w:
                            nd = dist[x2][y2] + 1
                            if C[v1][v2] != "#" and dist[v1][v2] == -1:
                                dist[v1][v2] = nd
                                queue.append([v1, v2])

solve([sh,sw])
print(dist[gh][gw])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 22 22:23:15 2020

@author: naoki
"""
def main():
    from collections import deque 
    H, W = map(int,input().split()) 
    Ch, Cw = map(int,input().split()) # 魔法使いの初期位置
    Dh, Dw = map(int,input().split()) # 目的地
    maze = ['#'*(W+4)]
    maze.append('#'*(W+4))
    for _ in range(H):
        maze.append('##' + input()[:-1] + '##')
    maze.append('#'*(W+4))
    maze.append('#'*(W+4))
    visited = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if maze[i][j] == '#':
                visited[i][j] = -2 
    Ch+=1
    Cw+=1
    Dh+=1
    Dw+=1
    visited[Ch][Cw] = 0 
    walk =[[1,0],[-1,0],[0,1],[0,-1]]
    telepo = [[i,j] for i in range(-2,3) for j in range(-2,3)]
    
    q_walk = deque([[Ch,Cw]])
    q_telepo = deque([])
    
    while q_walk:
        yw,xw = q_walk.popleft()
        #行った場所を管理
        q_telepo.append([yw,xw])
        for i,j in walk:
            ny,nx = yw + i, xw + j 
            if visited[ny][nx] == -1:
                #行ったことがなければワープ回数を代入する
                visited[ny][nx] = visited[yw][xw]
                q_walk.append([ny,nx])
        if len(q_walk) == 0:
            while q_telepo:
               yt,xt = q_telepo.popleft()
               for i,j in telepo:
                   my,mx = yt+i, xt+j
                   if visited[my][mx] == -1:
                       visited[my][mx] = visited[yt][xt] + 1
                       q_walk.append([my,mx])
    print(visited[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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not 0 <= nh <= H-1 and 0 <= nw <= W-1:
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not 0 <= nh <= H-1 and 0 <= nw <= W-1:
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
import sys
sys.setrecursionlimit(1000000)
f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
l=[input() for _ in range(h)]

queue=[]
queue.append([c1,c2])
visit=[[0]*w for _ in range(h)]

wapcnt=0
nokori=h+w-2
while True:
  while len(queue)>0:
    x,y=queue.pop(0)
    if x==d1 and y==d2:
      print(wapcnt)
      exit()
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      if 0<=x+i<=h-1 and 0<=y+j<=w-1:
        if visit[x+i][y+j]==0 and l[x+i][y+j]=='.':
          visit[x+i][y+j]=1
          queue.append([x+i,y+j])
          nokori=min(nokori,abs(x+i-d1)+abs(y+j-d2))
  if nokori<=4 and abs(x+i-d1)<=2 and abs(y+j-d2)<=2:
    wapcnt+=1
    print(wapcnt)
    exit()
  m=4
  ll=[]
  for p in range(-2,3):
    for q in range(-2,3):
      if 0<=x+p<h and 0<=y+q<w:
        if l[x+p][y+q]=='.' and visit[x+p][y+q]==0:
          if not p==q==0:
            m=min(m,abs(x+p-d1)+abs(y+q-d2))
            ll.append([p,q,abs(x+p-d1)+abs(y+q-d2)])
  if ll==[]:
    print(-1)
    exit()
  nokori-=m
  for lll in ll:
    if lll[2]==m:
      a=lll[0]
      b=lll[1]
  queue.append([x+a,y+b])
  wapcnt+=1

Submission status: Runtime Error

Solution code:
import sys
h,w = map(int,input().split())
ci,cj = map(int,input().split())
gi,gj = map(int,input().split())

C = [list(input()) for i in range(h)]
visited = [[-1 for i in range(w)] for i in range(h)]

ci=ci-1
cj=cj-1
gi=gi-1
gj=gj-1

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

def check(s_pos, d):
    queue = []
    queue.append(s_pos)
    visited[s_pos[0]][s_pos[1]] = d
    
    candidates = []
    while len(queue) > 0:
        pos = queue.pop(0)
        candidates.append(pos)
        if pos[0] == gi and pos[1] == gj:
            return
        for i in range(4):
            y = pos[0] + dy_dx[i][0]
            x = pos[1] + dy_dx[i][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != "#" and visited[y][x] == -1:
                    visited[y][x] = d
                    queue.append([y,x])
    
    while len(candidates) > 0:
        c = candidates.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                y = c[0] + i
                x = c[1] + j
                if 0 <= y < h and 0 <= x < w:
                    nd = d+1
                    if C[y][x] != "#" and visited[y][x] == -1:
                        check([y,x], nd)

check([ci,cj], 0)
print(visited[gi][gj])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = [input() for _ in range(H)]

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if score[(y+dy, x+dx)] > score[(y, x)]:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if score[(y+dy, x+dx)] > score[(y, x)]+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
h,w = map(int,input().split())
ci,cj = map(int,input().split())
gi,gj = map(int,input().split())

C = [list(input()) for i in range(h)]
visited = [[-1 for i in range(w)] for i in range(h)]

ci=ci-1
cj=cj-1
gi=gi-1
gj=gj-1

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

def check(s_pos, d):
    queue = []
    queue.append(s_pos)
    visited[s_pos[0]][s_pos[1]] = d
    
    candidates = []
    candidates.append(s_pos)
    while len(queue) > 0:
        pos = queue.pop(0)
        if pos[0] == gi and pos[1] == gj:
            return
        for i in range(4):
            y = pos[0] + dy_dx[i][0]
            x = pos[1] + dy_dx[i][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != "#" and (visited[y][x] == -1 or d < visited[y][x]):
                    visited[y][x] = d
                    queue.append([y,x])
                    candidates.append([y,x])
    
    while len(candidates) > 0:
        c = candidates.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                y = c[0] + i
                x = c[1] + j
                if 0 <= y < h and 0 <= x < w:
                    nd = d+1
                    if C[y][x] != "#" and (visited[y][x] == -1 or nd < visited[y][x]):
                        check([y,x], nd)

check([ci,cj], 0)
print(visited[gi][gj])

Submission status: Runtime Error

Solution code:
from collections import deque

if __name__ == '__main__':

    h,w = map(int,input().split())
    sh,sw = map(int,input().split())
    gh,gw = map(int,input().split())
    A = []
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    
    for _ in range(h):
        A.append(list(input()))

    #到着エリア専用
    INF = 10**19
    B = [[INF for _ in range(w)]for _ in range(h)]

    #deque登場
    d = deque()
    
    X = [0,1,0,-1]
    Y = [1,0,-1,0]
    
    #初期値設定
    d.appendleft([sh,sw])
    B[sh][sw] = 0
    
    while len(d) != 0:

        d1,d2 = d.popleft()
        dd = B[d1][d2]

        #コスト0で行ける距離
        for i in range(h):
            nx = d1 + X[i]
            ny = d2 + Y[i]
            #移動先が枠をはみ出るなら次
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if A[nx][ny] == "#":
                continue
            if B[nx][ny] <= dd:
                continue

            #コストを設定
            B[nx][ny] = dd
            #次の位置を設定
            d.appendleft([nx,ny])


        #魔法を使う必要がある距離
        for j in range(-2,3):
            for k in range(-2,3):
                nx = d1 + j
                ny = d2 + k
                #移動先が枠をはみ出るなら次
                if nx < 0 or ny < 0 or nx >= h or ny >= w:
                    continue
                if A[nx][ny] == "#":
                    continue
                if B[nx][ny] <= dd + 1:
                    continue

                #コストを設定
                B[nx][ny] = dd + 1

                #次の位置を設定
                d.append([nx,ny])

    ans = B[gh][gw]
    if ans == INF:
        ans = -1
    print(ans)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        di, dj = d_b[v][0]+i, d_b[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i, 0] = 0
    dist[i, -1] = 0
for j in range(w+2):
    dist[0, j] = 0
    dist[-1, j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import sys

def in_grid(temp, h, w, s):
	if 0 <= temp[0] and temp[0] < w and 0 <= temp[1] and temp[1] < h:
		return s[temp[0]][temp[1]] == "."
	return False

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 = [list(input()) for i in range(h)]

drc = [[1,0], [-1,0], [0,1], [0,-1]]
openl = [[0, ch, cw]]
closel = []

while True:
	if not openl:
		break
	
	now = heapq.heappop(openl)
	if now[1] == dh and now[2] == dw:
		print(now[0])
		sys.exit()

	heapq.heappush(closel, [now[1], now[2]])
	for i in drc:
		temp = [now[1] + i[0], now[2] + i[1]]
		if in_grid(temp, h, w, s) and not temp in closel:
			heapq.heappush(openl, [now[0], temp[0], temp[1]])
	
	for i in range(0, 3):
		for k in range(0, 3):
			temp = [now[1] + i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] + i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
				
print(-1)

Submission status: Runtime Error

Solution code:
import heapq
import sys

def in_grid(temp, h, w, s):
	if 0 <= temp[0] and temp[0] < w and 0 <= temp[1] and temp[1] < h:
		return s[temp[0]][temp[1]] == "."
	return False

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 = [list(input()) for i in range(h)]

drc = [[1,0], [-1,0], [0,1], [0,-1]]
openl = [[0, ch, cw]]
closel = []

while True:
	if not openl:
		break
	
	now = heapq.heappop(openl)
	if now[1] == dh and now[2] == dw:
		print(now[0])
		sys.exit()

	heapq.heappush(closel, [now[1], now[2]])
	for i in drc:
		temp = [now[1] + i[0], now[2] + i[1]]
		if in_grid(temp, h, w, s) and not temp in closel:
			heapq.heappush(openl, [now[0], temp[0], temp[1]])
	
	for i in range(1, 3):
		for k in range(1, 3):
			temp = [now[1] + i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] + i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
				
print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = ["" for _ in range(W)]
for i in range(H):
  Shw[i] = input()

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

while len(d) > 0:
  
  here = d.popleft()
      
  # 右のマス
  if here[1] != W-1:
    if (here[0], here[1]+1) not in score or ((here[0], here[1]+1) in score and (score[(here[0], here[1]+1)] > score[here])):
      if Shw[here[0]][here[1]+1] == ".":
        d.appendleft((here[0], here[1]+1))
        score[(here[0], here[1]+1)] = score[here]

  # 下のマス
  if here[0] != H-1:
    if (here[0]+1, here[1]) not in score or ((here[0]+1, here[1]) in score and (score[(here[0]+1, here[1])] > score[here])):
      if Shw[here[0]+1][here[1]] == ".":
        d.appendleft((here[0]+1, here[1]))
        score[(here[0]+1, here[1])] = score[here]
  
  # 左のマス
  if here[1] != 0:
    if (here[0], here[1]-1) not in score or ((here[0], here[1]-1) in score and (score[(here[0], here[1]-1)] > score[here])):
      if Shw[here[0]][here[1]-1] == ".":
        d.appendleft((here[0], here[1]-1))
        score[(here[0], here[1]-1)] = score[here]
    
  # 上のマス
  if here[0] != 0:
    if (here[0]-1, here[1]) not in score or ((here[0]-1, here[1]) in score and (score[(here[0]-1, here[1])] > score[here])):
      if Shw[here[0]-1][here[1]] == ".":
        d.appendleft((here[0]-1, here[1]))
        score[(here[0]-1, here[1])] = score[here]
  
  # ワープのマス
  for i in range(here[0]-2, here[0]+3, 1):
    if i < 0 or i > H-1:
      continue
    for j in range(here[1]-2, here[1]+3, 1):
      if j < 0 or j > W-1 or (i, j) in score:
        continue
      else:
        if Shw[i][j] == ".":
          d.append((i, j))
          score[(i, j)] = score[here] + 1

#print(score)
if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)