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:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1, b1
from heapq import heappop, heappush

#@njit(i8(b1[:,:], i8, i8, i8, i8), cache=True)
def solve(grid, ch, cw, dh, dw):
    h, w = grid.shape
    
    dist = np.full((h, w), INF, dtype=np.int64)
    dist[ch][cw] = 0

    que = [(0, ch, cw)]

    while que:
        cnt, y, x = heappop(que)

        if y == dh and x == dw:
            break

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue

                if abs(dx) == 2 or abs(dy) == 2 or (abs(dx) == 1 and abs(dy) == 1):
                    warp = 1
                else:
                    warp = 0

                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= w or ny < 0 or ny >= h or grid[ny][nx]:
                    continue
                
                if dist[ny][nx] > cnt + warp:
                    dist[ny][nx] = cnt + warp
                    heappush(que, (cnt + warp, ny, nx))

    if dist[dh][dw] == INF:
        return - 1
    else:
        return dist[dh][dw]


def Main():
    H, W = read_ints()
    ch, cw = read_ints(); ch -= 1; cw -= 1
    dh, dw = read_ints(); dh -= 1; dw -= 1

    grid = np.array([[g == '#' for g in read_str()] for _ in range(H)])
    
    print(solve(grid, ch, cw, dh, dw))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve','(i8(b1[:,:], i8, i8, i8, i8)')(solve)
    cc.compile()

if __name__ == '__main__':
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit()
    from my_module import solve
    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 = [input() for i in range(H)]
INF = float('inf')

dist = [[INF] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.popleft()
        d = dist[y][x]
        flag = 0
        for vx,vy in walk:
            nx = x + vx
            ny = y + vy
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if S[ny][nx] == '.':
                    if dist[ny][nx] > d:
                        dist[ny][nx] = d
                        queue.append([nx,ny])
                else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.popleft()
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[ny][nx] == '.' and dist[ny][nx] == 10**9+7:
                        dist[ny][nx] = dist[y][x] + 1
                        queue.append([nx,ny])
                
if dist[Dh][Dw] != INF:
    print(dist[Dh][Dw])
else:
    print(-1)

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

dist = [[10**9+7 for _ in range(W)] for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = []
queue.append([Ch,Cw])
queue2 = []
dist[Ch2][Cw2] = 0
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.pop(0)
        d = dist[x][y]
        flag = 0
        for vx in range(-1,2):
            for vy in range(-1,2):
                if [vx,vy] in [[1,1],[1,-1],[-1,-1],[-1,1]]:
                    continue
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny < W:
                    if S[nx][ny] == '.':
                        if dist[nx][ny] > d:
                            dist[nx][ny] = d
                            queue.append([nx,ny])
                    else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.pop(0)
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[nx][ny] == '.' and dist[nx][ny] == 10**9+7:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append([nx,ny])
                
print(dist[Dh][Dw])

Submission status: Runtime Error

Solution code:
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z:
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
            fast += 1
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i; ny = y+j
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z+1:
                    nq.append([nx,ny,z+1])
                    mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


idx=0
while i==len(nxt):
    i=nxt[idx]
    i+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
    [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
    [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
    [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
q = deque([ch, cw])
one_time = deque()
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def chk():
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in ((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        if s[i,j]=='.': 
            q.append([i,j])
            s[i,j]=int(s[a,b])
        elif len(wq)==0 or (len(wq)>0 and wq[-1]!=[a,b]):
            wq.append([a,b])
    chk()
    return

def worp(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    chk()
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)
bfs(ch,cw)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    
    mylist = [input().rstrip() for i in range(H)]
    dist = Init(H, W, float('inf'))
    #dist2 = Init(H, W, float('inf'))
    dq = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
        #コスト1の移動
        for x2, y2 in move2:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]+1:
                dist[x2][y2] = dist[x][y]+1
                dq.append((x2,y2))
                
        #コスト0の移動
        for x2, y2 in move1:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]:
                dist[x2][y2] = dist[x][y]
                dq.append((x2,y2))
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def chk():
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in ((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        if s[i,j]=='.': 
            q.append([i,j])
            s[i,j]=int(s[a,b])
        else:
            wq.append([a,b])
    chk()
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    chk()
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)
bfs(ch,cw)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def chk():
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in ((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        f=0
        if s[i,j]=='.': 
            f=1
            q.append([i,j])
            s[i,j]=int(s[a,b])
        if f==0:
            wq.append([a,b])
    chk()
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    chk()
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)
bfs(ch,cw)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

# 各頂点を変換
def alter(y, x):
    return H * y + x

pos = []

# エッジ生成
for y in range(H):
    for x in range(W):
        if maze[y][x] == '#':
            continue
        # walkingエッジ
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.':
                pos.append([alter(y, x), alter(ny, nx), 0])
        # warpエッジ
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                if w_y == 0 and w_x == 0:
                    continue
                wy = y + w_y
                wx = x + w_x
                if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == '.':
                    pos.append([alter(y, x), alter(wy, wx), 1])

# 木の生成
def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b, c = edge_list[i]
        G[a].append([b, c])
        # G[b].append([a, c])
        # G[a - 1].append([b - 1, c])
        # G[b - 1].append([a - 1, c])

    """
    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            #leaves.append(i)
    """

    return G

edges = build_tree_dis(H * W, pos)

# ダイクストラ
def dij(start, goal, size):
    dist = [float('inf') for i in range(size)]
    dist[start] = 0
    pq = [(0, start)]

    # pqの先頭がgoal行きのものなら最短距離を返す
    while len(pq) > 0:
        d, now = heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heappush(pq, (dist[i[0]], i[0]))
    return dist[goal]

ans = dij(alter(Ch, Cw), alter(Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

# 各頂点を変換
def alter(y, x):
    return H * y + x

pos = []

# エッジ生成
for y in range(H):
    for x in range(W):
        if maze[y][x] == '#':
            continue
        # walkingエッジ
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.':
                pos.append([alter(y, x), alter(ny, nx), 0])
        # warpエッジ
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                if w_y == 0 and w_x == 0:
                    continue
                wy = y + w_y
                wx = x + w_x
                if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == '.':
                    pos.append([alter(y, x), alter(wy, wx), 1])

# 木の生成
def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b, c = edge_list[i]
        G[a].append([b, c])
        # G[b].append([a, c])
        # G[a - 1].append([b - 1, c])
        # G[b - 1].append([a - 1, c])

    """
    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            #leaves.append(i)
    """

    return G

edges = build_tree_dis(H * W, pos)

# ダイクストラ
def dij(start, goal, size):
    dist = [float('inf') for i in range(size)]
    dist[start] = 0
    pq = [(0, start)]

    # pqの先頭がgoal行きのものなら最短距離を返す
    while len(pq) > 0 and (pq[0][1] != goal):
        d, now = heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heappush(pq, (dist[i[0]], i[0]))
    if len(pq) == 0:
        return -1
    else:
        return pq[0][0]

print(dij(alter(Ch, Cw), alter(Dh, Dw), H * W))

Submission status: Runtime Error

Solution code:
def solve():
    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 = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input()[:-1] + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))
    
    
    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
             (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
             (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
             (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
        
    not_yet = [(ch, cw)]
    one_time = []
    
    while len(not_yet) > 0:
        x, y = not_yet.pop()
        one_time.append((x, y))
        for (p, q) in move:
            v1, v2 = x+p, y+q
            if ans[v1][v2] == -1:
                not_yet.append((v1, v2))
                ans[v1][v2] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.pop()
                for (v1, v2) in move2:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        not_yet.append((i, j))
    print(ans[dh][dw])
      
solve()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(100000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[start[0]][start[1]] = 0
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            cost[i][j] = c
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            cost[i][j] = c
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            cost[i + di][j + dj] = c
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()

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

dist = [[-1 for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            dist[h][w] = -2
Ch2 = Ch-1
Cw2 = Cw-1
Dh2 = Dh-1
Dw2 = Dw-1

queue = []
queue.append([Ch2,Cw2])
queue2 = []
dist[Ch2][Cw2] = 0
    
while len(queue) > 0:
    x, y = queue.pop(0)
    if x == Dw and y == Dh:
        break
    queue2.append([x,y])
    for vx in range(-1,2):
        for vy in range(-1,2):
            nx = x + vx
            ny = y + vy
            if abs(vx) == abs(vy):
                continue
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if dist[nx][ny] != '#' and dist[nx][ny] == -1:
                    queue.append([nx,ny])
                    dist[nx][ny] = dist[x][y]
                    
    if len(queue) == 0:
        while len(queue2) > 0:
            x, y = queue2.pop(0)
            if x == Dw and y == Dh:
                break
            for vx in range(-2,3):
                for vy in range(-2,3):
                    nx = x + vx
                    ny = y + vy
                    if 0 <= nx and nx < W and 0 <= ny and ny < H:
                        if dist[nx][ny] != '#' and dist[nx][ny] == -1:
                            queue.append([nx,ny])
                            dist[nx][ny] = dist[x][y] + 1
                
print(dist[Dh2][Dw2])

Submission status: Runtime Error

Solution code:
from sys import stdin

def main():
    from collections import deque
    input = stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    s = [[-1] * (w + 4) for _ in range(h + 4)]
    for j in range(2, h + 2):
        t = input()
        for i in range(w):
            if t[i] == ".":
                s[j][i + 2] = 0
    u = [[-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]
    ]
    que = deque([])
    wqu = deque([])
    que.append(cw + 1)
    que.append(ch + 1)
    s[ch + 1][cw + 1] = 1
    while len(que) > 0 or len(wqu) > 0:
        while len(que) > 0:
            y = que.popleft()
            x = que.popleft()
            cnt = s[y][x]
            if s[y + 1][x] == 0:
                s[y + 1][x] = cnt
                que.append(x)
                que.append(y + 1)
            elif s[y + 1][x] == -1:
                wqu.append(x)
                wqu.append(y)
            if s[y - 1][x] == 0:
                s[y - 1][x] = cnt
                que.append(x)
                que.append(y - 1)
            elif s[y - 1][x] == -1:
                wqu.append(x)
                wqu.append(y)
            if s[y][x + 1] == 0:
                s[y][x + 1] = cnt
                que.append(x + 1)
                que.append(y)
            elif s[y][x + 1] == -1:
                wqu.append(x)
                wqu.append(y)
            if s[y][x - 1] == 0:
                s[y][x - 1] = cnt
                que.append(x - 1)
                que.append(y)
            elif s[y][x - 1] == -1:
                wqu.append(x)
                wqu.append(y)
        while len(wqu) > 0:
            y = wqu.popleft()
            x = wqu.popleft()
            cnt = s[y][x]
            for j, i in u:
                if s[y + j][x + i] == 0:
                    s[y + j][x + i] = cnt + 1
                    que.append(x + i)
                    que.append(y + j)
    print(s[dh + 1][dw + 1] - 1)
main()

Submission status: Runtime Error

Solution code:
def main(H, W, C, D, S):
    def inside(x, y):
        return ((0 <= x and x < H) and (0 <= y and y < W))

    def isroad(x, y):
        return S[x][y] == '.'

    C, D = list(map(lambda x:(x[0]-1, x[1]-1), [C, D])) # python方式に直す


    next = {C}
    masu = [[-1 for _ in range(W)] for __ in range(H)]

    def moverange(x, y):
        return inside(x, y) and masu[x][y] == -1 and isroad(x, y)

    def func(now, kaisu):
        for canmove in {(x-1, y), (x+1, y), (x, y+1), (x, y-1)}:
            if moverange(*canmove):
                # que.append(canmove)
                que.add(canmove)
                masu[canmove[0]][canmove[1]] = kaisu

    def make_st(x, y):
        return {(x+i, y+j) for i in range(-2, 3) for j in range(-2, 3)}

    kaisu = -1
    while len(next) != 0:
        kaisu += 1
        que = next
        next = set()
        while que:
            now = que.pop()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            func(now, kaisu)

            for canmove in make_st(*now):
                if moverange(*canmove):
                    next.add(canmove)
    ans = masu[D[0]][D[1]]
    print(ans)


if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [input() for _ in range(H)]
    main(H, W, C, D, S)