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:
from heapq import heappush, heappop

R = lambda: map(int, input().split())

H, W = R()
f = lambda x, y: (x - 2) * H + y - 2
s, t = (f(*(x + 1 for x in R())) for _ in (0, 0))
a =  ['#' * (W + 4)] * 4
a[2: 2] = ['##' + input() + '##' for _ in range(H)]
g = [[] for _ in range(H * W)]
for i in range(2, H + 2):
  for j in range(2, W + 2):
    if a[i][j] == '.':
      x = f(i, j)
      for k in range(i - 2, i + 3):
        for l in range(j - 2, j + 3):
          y = f(k, l)
          if x != y and a[k][l] == '.':
            w = abs(k - i) + abs(l - j) > 1
            g[x].append((y, w))
            g[y].append((x, w))

inf = 9**9            
dist = H * W * [inf]
dist[s] = 0
hp = []
heappush(hp, (0, s))
while hp:
  _, u = heappop(hp)
  for v, w in g[u]:
    if dist[v] > dist[u] + w:
      dist[v] = dist[u] + w
      heappush(hp, (dist[v], v))
print((-1, dist[t])[dist[t] < inf])

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
CH, CW = tuple(int(x) - 1 for x in input().split())
DH, DW = tuple(int(x) - 1 for x in input().split())
maze = [input() for _ in range(W)]

WALK = [(0, 1), (0, -1), (-1, 0), (1, 0)]
WARP = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + WALK]

INF = 10 ** 12
cost = [[INF] * W for _ in range(H)]
q = deque()

cost[CH][CW] = 0
q.append((CH, CW, 0))

while q:
	x, y, s = q.popleft()
	for dx, dy in WALK:
		nx, ny = x + dx, y + dy
		if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and cost[nx][ny] > s:
			cost[nx][ny] = s
			q.appendleft((nx, ny, s))
	for dx, dy in WARP:
		nx, ny = x + dx, y + dy
		if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and cost[nx][ny] > s + 1:
			cost[nx][ny] = s + 1
			q.appendleft((nx, ny, s + 1))
ans = cost[DH][DW] if cost[DH][DW] < INF else '-1'
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
from math import ceil
import numpy as np


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w = nm()
    Ch, Cw = nm()
    Dh, Dw = nm()
    S = np.array([list(ns()) for _ in range(h)])
    can_go = [(Ch, Cw)]
    pos = deque([(Ch, Cw)])
    visited = [[0] * w for _ in range(h)]
    visited[Ch - 1][Cw - 1] = 1

    while pos:
        c_i, c_j = pos.pop()
        for i, j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
            if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w and not visited[c_i + i - 1][c_j + j - 1]:
                if S[c_i + i - 1][c_j + j - 1] == '.':
                    can_go.append((c_i + i, c_j + j))
                    pos.append((c_i + i, c_j + j))
                    visited[c_i + i - 1][c_j + j - 1] = 1

    if (Dh, Dw) in can_go:
        print(0)
        return

    cost = [[float('Inf')] * w for _ in range(h)]

    for i, j in can_go:
        cost[i - 1][j - 1] = 0

    warp = deque(can_go)

    while warp:
        c_i, c_j = warp.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                        and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] + 1 \
                        and S[c_i + i - 1][c_j + j - 1] == '.':
                    cost[c_i + i - 1][c_j + j - 1] = cost[c_i - 1][c_j - 1] + 1
                    warp.append((c_i + i, c_j + j))

    print(cost[Dh - 1][Dw - 1] if cost[Dh - 1][Dw - 1] != float('Inf') else -1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
H,W = list(map(int,input().split()))
start = list(map(lambda x:int(x)-1,input().split()))
goal = list(map(lambda x:int(x)-1,input().split()))
A = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
B = deque([[start[0],start[1],0]])
warp = []
for i in range(-2,3):
    for j in range(-2,3):
            warp.append([i,j])

num = 0
# print(start,warp)
while 1:
    y,x,n = B.popleft()
    if visited[y][x] == 1:continue
    if [y,x] == goal:
        num = n
        break
    visited[y][x] = 1
    for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.appendleft([y+dy,x+dx,n])
    for dy,dx in warp:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.append([y+dy,x+dx,n+1])
    if not B:
        num = -1
        break

print(num)

Submission status: Runtime Error

Solution code:
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C_h, C_w = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C_h, C_w]])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      i += move_h
      j += move_w
      if 0 <= i <= H-1 and 0 <= j <= W-1 and S[i][j] == '.' and (not check_visited[i][j]) :
         dq.appendleft([d, i, j])
   for move_h in range(-2, 3):
      for move_w in range(-2, 3):
         if [move_h, move_w] == [0, 0]:
            continue
         i += move_h
         j += move_w
         if 0 <= i <= H-1 and 0 <= j <= W-1 and S[i][j] == '.' and (not check_visited[i][j]) :
            dp.append([d+1, i, j])
print(-1)

Submission status: Runtime Error

Solution code:
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C_h, C_w = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([0, C_h, C_w])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      i += move_h
      j += move_c
      if 0 <= i <= H-1 and 0 =< j <= W-1 and S[i][j] == '.' and (not check_visited[i][j]) :
         dq.appendleft([d, i, j])
   for move_h in range(-2, 3):
      for move_c in range(-2, 3):
         if move_h, move_c == 0, 0:
            continue
         i += move_h
         j += move_c
         if 0 <= i <= H-1 and 0 =< j <= W-1 and S[i][j] == '.' and (not check_visited[i][j]) :
            dp.append([d+1, i, j])
print(-1)

Submission status: Runtime Error

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x+1, y+1)

    y, x = map(int, input().split())
    goal = (x+1, y+1)

    dist_table = [[-2] * (W+2)]
    dist_table.append([-2] * (W+2))
    for _ in range(H):
        row = '##' + input() + '##'
        row = [-1 if c == '.' else -2 for c in row]
        dist_table.append(row)
    dist_table.append([-2] * (W+2))
    dist_table.append([-2] * (W+2))



    sx, sy = start
    dist_table[sy][sx] = 0

    move1 = ((-1, 0), (1, 0), (0, 1), (0, -1))
    move2 = ((-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))

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
from heapq import *
#from numba import jit

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = np.array([input() for i in range(H)])

walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i ,j])
inf = float("inf")
table = np.array([[inf for i in range(W)] for i in range(H)])
table[Ch-1, Cw-1] = 0
queue = [(Ch-1, Cw-1, 0)]

def main():
  while queue:
    x, y, cost = heappop(queue)
    for i, j in walk_move:
      dx = x+i
      dy = y+j
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
        table[dx][dy] = cost
        heappush(queue, (dx, dy, cost))
    for k, l in magic_move:
      dx = x+k
      dy = y+l
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
        table[dx][dy] = cost+1
        heappush(queue, (dx, dy, cost+1))
  return table[Dh-1][Dw-1]
        
ans = main()
if ans == inf:
  print("-1")
else:
  print(int(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        print(next_q)
        if h == glh and w == glw:
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    dist[ni][nj]=nk
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            heappush(hp,(nk,ni,nj))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
def good(x,y):
    if (x>=0 and x<h) and (y>=0 and y<w):
        return (mat[x][y] != "#")
h, w = map(int,input().split())
sh, sw = map(int,input().split())
eh, ew = map(int,input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)
x = [1,-1,0,0]
y = [0,0,-1,1]
dist = [[float('inf') for i in range(w)]for j in range(h)]
sh -= 1
sw -= 1
eh -= 1
ew -= 1
dist[sh][sw] = 0
queue = deque()
queue.appendleft((sh,sw))
while queue:
    m = queue.popleft()
    for d in range(4):
        nx = m[0] + x[d]
        ny = m[1] + y[d]
        if not good(nx,ny):
            continue
        if dist[nx][ny] > dist[m[0]][m[1]]:
            dist[nx][ny] =  dist[m[0]][m[1]]
            queue.appendleft((nx,ny))
    for i in range(m[0]-2,m[1]+3):
        for j in range(m[1]-2,m[1]+3):
            if not good(nx,ny):
                continue
            if dist[i][j] > dist[m[0]][m[1]] + 1:
                dist[i][j] = dist[m[0]][m[1]] + 1
                queue.append((i,j))
if dist[eh][ew] == float('inf'):
    print(-1)
else:
    print(dist[eh][ew])

Submission status: Runtime Error

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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())
maze = [list(input()) for _ in range(h)]
visited = [[-1]*w for _ in range(h)]

# コスト0で移動できるマスを列挙
def bfs_walk(sy, sx):
    global maze, visited
    d = collections.deque([[sy, sx]])
    rect = [[sy, sx]]
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        for i, j in ([(0,1),(0,-1),(1,0),(-1,0)]):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = 0
                    d.append([newy, newx])
                    rect.append([newy, newx])
    return rect

# 魔法で移動できるマスを列挙
def bfs_magic(sy, sx):
    global maze, visited
    rect = [[sy, sx]]
    x, y = sy, sx
    visited[sy][sx] = 0
    for i in range(-2, 3):
        for j in range(-2, 3):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = visited[y][x]+1
                    rect.append([newy, newx])
    return rect

def solve():
    cost = 0
    sy, sx = ch, cw
    d = collections.deque()
    use_walk = bfs_walk(sy, sx)
    while True:
        if [dh, dw] in use_walk:
            print(cost)
            break
        cost += 1
        use_magic = list()
        for i in use_walk:
            use_magic.append(bfs_magic(i[0], i[1]))
        use_magic = [i for l in use_magic for i in l]
        if [dh, dw] in use_magic:
            print(cost)
            break
        use_walk = list()
        for i in use_magic:
            use_walk.append(bfs_walk(i[0], i[1]))
        use_walk = [i for l in use_walk for i in l]
    return 0

if __name__ == "__main__":
    solve()

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())
maze = [list(input()) for _ in range(h)]
visited = [[-1]*w for _ in range(h)]

# コスト0で移動できるマスを列挙
def bfs_walk(sy, sx):
    global maze, visited
    d = collections.deque([[sy, sx]])
    rect = [[sy, sx]]
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        for i, j in ([(0,1),(0,-1),(1,0),(-1,0)]):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = 0
                    d.append([newy, newx])
                    rect.append([newy, newx])
    return rect

# 魔法で移動できるマスを列挙
def bfs_magic(sy, sx):
    global maze, visited
    rect = [[sy, sx]]
    x, y = sy, sx
    visited[sy][sx] = 0
    for i in range(-2, 3):
        for j in range(-2, 3):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = visited[y][x]+1
                    rect.append([newy, newx])
    return rect

def solve():
    cost = 0
    sy, sx = ch, cw
    d = collections.deque()
    use_walk = bfs_walk(sy, sx)
    while True:
        if [dh, dw] in use_walk:
            print(cost)
            break
        cost += 1
        use_magic = list()
        for i in use_walk:
            use_magic.append(bfs_magic(i[0], i[1]))
        use_magic = [i for l in use_magic for i in l]
        if [dh, dw] in use_magic:
            print(cost)
            break
        use_walk = list()
        for i in use_magic:
            use_walk.append(bfs_walk(i[0], i[1]))
        use_walk = [i for l in use_walk for i in l]
    for i in visited:
        print(i)
    return 0

if __name__ == "__main__":
    solve()
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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())
maze = [list(input()) for _ in range(h)]
visited = [[-1]*w for _ in range(h)]

# コスト0で移動できるマスを列挙
def bfs_walk(sy, sx):
    global maze, visited
    d = collections.deque([[sy, sx]])
    rect = [[sy, sx]]
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        for i, j in ([(0,1),(0,-1),(1,0),(-1,0)]):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = 0
                    d.append([newy, newx])
                    rect.append([newy, newx])
    return rect

# 魔法で移動できるマスを列挙
def bfs_magic(sy, sx):
    global maze, visited
    rect = [[sy, sx]]
    x, y = sy, sx
    visited[sy][sx] = 0
    for i in range(-2, 3):
        for j in range(-2, 3):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = visited[y][x]+1
                    rect.append([newy, newx])
    return rect

def solve():
    cost = 0
    sy, sx = ch, cw
    d = collections.deque()
    use_walk = bfs_walk(sy, sx)
    while True:
        if [dh, dw] in use_walk:
            print(cost)
            break
        cost += 1
        use_magic = list()
        for i in use_walk:
            use_magic.append(bfs_magic(i[0], i[1]))
        use_magic = [i for l in use_magic for i in l]
        if [dh, dw] in use_magic:
            print(cost)
            break
        use_walk = list()
        for i in use_magic:
            use_walk.append(bfs_walk(i[0], i[1]))
        use_walk = [i for l in use_walk for i in l]
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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())
maze = [list(input()) for _ in range(h)]
visited = [[-1]*w for _ in range(h)]

# コスト0で移動できるマスを列挙
def bfs_walk(sy, sx):
    global maze, visited
    d = collections.deque([[sy, sx]])
    rect = [[sy, sx]]
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        for i, j in ([(0,1),(0,-1),(1,0),(-1,0)]):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = 0
                    d.append([newy, newx])
                    rect.append([newy, newx])
    return rect

# 魔法で移動できるマスを列挙
def bfs_magic(sy, sx):
    global maze, visited
    rect = [[sy, sx]]
    x, y = sy, sx
    visited[sy][sx] = 0
    for i in range(-2, 3):
        for j in range(-2, 3):
            newy, newx = y+i, x+j
            if newy < 0 or newx < 0:
                continue
            elif newy >= h or newx >= w:
                continue
            elif visited[newy][newx] == -1:
                if maze[newy][newx] == ".":
                    visited[newy][newx] = visited[y][x]+1
                    rect.append([newy, newx])
    return rect

def solve():
    cost = 0
    sy, sx = ch, cw
    d = collections.deque()
    use_walk = bfs_walk(sy, sx)
    while True:
        if [dh, dw] in use_walk:
            print(cost)
            break
        cost += 1
        use_magic = list()
        for i in use_walk:
            use_magic.append(bfs_magic(i[0], i[1]))
        use_magic = [i for l in use_magic for i in l]
        if [dh, dw] in use_magic:
            print(cost)
            break
        use_walk = list()
        for i in use_magic:
            use_walk.append(bfs_walk(i[0], i[1]))
        use_walk = [i for l in use_walk for i in l]
    for i in visited:
        print(i)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np
from heapq import heappop, heappush


def solve(h, w, s, t, field):
    WARP = (-(w * 2 + 10), -(w * 2 + 9), -(w * 2 + 8), -(w * 2 + 7), -(w * 2 + 6),
            -(w + 6), -(w + 5), -(w + 3), -(w + 2),
            -2, 2,
            w + 2, w + 3, w + 5, w + 6,
            w * 2 + 6, w * 2 + 7, w * 2 + 8, w * 2 + 9, w * 2 + 10)
    WALK = (-(w + 4), -1, 1, w + 4)

    qc = np.zeros(1000000, dtype=np.int32)
    qv = np.zeros(1000000, dtype=np.int32)
    qv[0] = s
    l, r = 0, 1
    visited = np.zeros((h + 4) * (w + 4), np.int8)
    queued = np.zeros((h + 4) * (w + 4), np.int8)
    queued[s] = 1
    while l < r:
        cost = qc[l]
        v = qv[l]
        l += 1
        if v == t:
            return cost
        if visited[v]:
            continue
        visited[v] = 1
        for d in WALK:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            queued[u] = 1
            l -= 1
            qc[l] = cost
            qv[l] = u
        for d in WARP:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            qc[r] = cost + 1
            qv[r] = u
            r += 1

    return -1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8,i8,i1[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8,i8,i8,i8,i1[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w = map(int, sys.stdin.readline().split())
ch, cw = map(int, sys.stdin.readline().split())
dh, dw = map(int, sys.stdin.readline().split())
field = np.ones((h + 4) * (w + 4), dtype=np.int8)
for i in range(h):
    line = sys.stdin.readline().strip()
    field[(i + 2) * (w + 4) + 2:(i + 2) * (w + 4) + w + 2] = list(map('.#'.index, line))
s = (ch + 1) * (w + 4) + cw + 1
t = (dh + 1) * (w + 4) + dw + 1
ans = solve(h, w, s, t, field)
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
import math
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
grid=[]
for i in range(h):
    arr=list(input())
    grid.append(arr)

dist=[[math.inf]*w for _ in range(h)]
q=deque()
q.append((sx,sy))
dist[sx][sy]=0
k=[[0,1],[0,-1],[1,0],[-1,0]]

while q:
    x,y=q.popleft()
    d=dist[x][y]
    for i,j in k:
        nx,ny=x+i,y+j
        if  nx<0 or nx>=w or ny<0 or ny>=h:
            continue
        if grid[nx][ny]=="#":
            continue
        if dist[nx][ny]<=d:
            continue
        dist[nx][ny]=d
        q.appendleft([nx,ny])
    
    for ei in range(-2,3):
        for ej in range(-2,3):
            nx,ny=x+ei,y+ej
            #print(nx,ny)
            if  nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if grid[nx][ny]=="#":
                continue
            if dist[nx][ny]<=d+1:
                continue
            dist[nx][ny]=d+1
            q.append([nx,ny])

if dist[gx][gy]==math.inf:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Runtime Error

Solution code:
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C_h, C_w = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([0, C_h, C_w])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      i += move_h
      j += move_c
      if 0 =< i <= H-1 and 0 =< j <= W-1 and (not check_visited[i][j]) and S[i][j] == '.':
         dq.appendleft([d, i, j])
   for move_h in range(-2, 3):
      for move_c in range(-2, 3):
         if move_h, move_c == 0, 0:
            continue
         i += move_h
         j += move_c
         if 0 =< i <= H-1 and 0 =< j <= W-1 and (not check_visited[i][j]) and S[i][j] == '.':
            dp.append([d+1, i, j])
print(-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())
s = [input() for i in range(H)]

def BFS(x,y):
    weight = {(x,y):0}
    checklist = []
    checked = []
    checklist = deque([[0,x,y]])
    while(len(checked)<H*W):
        while(1):
            weight_node,node_x,node_y = checklist.popleft()
            if (node_x,node_y) not in checked:
                checked.append((node_x,node_y))
                break
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        for next_x in range(max(0,node_x-2),min(H,node_x+3)):
                for next_y in range(max(0,node_y-2),min(W,node_y+3)):
                    if next_x == node_x and next_y == node_y:
                        continue
                    elif s[next_x][next_y] == '.':
                        if (next_x,next_y) in [(node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)]:
                            if (next_x,next_y) not in checked:
                                if (next_x,next_y) not in weight or weight_node < weight[(next_x,next_y)]:
                                    checklist.appendleft([weight_node,next_x,next_y])
                        else:
                            weight_next_node = weight_node + 1
                            if (next_x,next_y) not in checked:
                                if (next_x,next_y) not in weight or weight_node < weight[(next_x,next_y)]:
                                    checklist.append([weight_next_node,next_x,next_y])
    return -1

print(BFS(ch-1,cw-1))

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for i in range(H)]

def dijkstra(x,y):
    weight = {(x,y):0}
    checklist = []
    checked = []
    heappush(checklist,[0,x,y])
    while(len(checked) < H*W):
        weight_node,node_x,node_y = heappop(checklist)
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        checked.append((node_x,node_y))
        for next_x in range(max(0,node_x-2),min(H,node_x+3)):
                for next_y in range(max(0,node_y-2),min(W,node_y+3)):
                    if next_x == node_x and next_y == node_y:
                        continue
                    elif s[next_x][next_y] == '.':
                        if (next_x,next_y) in [(node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)]:
                            weight_next_node = weight_node
                        else:
                            weight_next_node = weight_node + 1
                        if (next_x,next_y) not in weight or weight_next_node < weight[(next_x,next_y)]:
                            #print(next_x,next_y)
                            weight[(next_x,next_y)] = weight_next_node
                            heappush(checklist,[weight_next_node,next_x,next_y])
    return -1

print(dijkstra(ch-1,cw-1))