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 itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[w][h]でアクセス すなわちy,x
    exit()
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    exit()
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    from array import array

    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())

    m = array('u', sum([list(input()) for _ in range(h)], []))
    vis = array('b', [0] * (h * w))

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y * h + x]:
                continue
            vis[y * h + x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                    if m[(y + s) * h + x + t] == '#':
                        edge.append((y, x))
                        continue
                    q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh * h + dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if vis[(y + s) * h + x + t]:
                        continue
                    if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                        if m[(y + s) * h + x + t] == '#':
                            continue
                        nx += walk(y + s, x + t)
                        if vis[dh * h + dw]:
                            return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -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=[[i,j] for j in range(0)]
for i in range(H):
    S.append(list(input()))

cost=[[-1 for i in range(W)] for j in range(H)]
queue = [[Ch-1, Cw-1] for j in range(1)]
queue2 = [[] for j in range(0)]
costCount = 1
cost[Ch-1][Cw-1]=0

while(cost[Dh-1][Dw-1]<0 and len(queue)>0):
    while(len(queue)>0):
        posX = queue[0][0]
        posY = queue[0][1]
        #print(posX,posY)
        queue2.append(queue.pop(0))
        if posX+1<H:
            if cost[posX+1][posY]<0 and S[posX+1][posY]==".":
                cost[posX+1][posY] = cost[posX][posY]
                queue.append([posX+1,posY])
        if posY+1<W:
            if cost[posX][posY+1]<0 and S[posX][posY+1]==".":
                cost[posX][posY+1] = cost[posX][posY]
                queue.append([posX,posY+1]) 
        if posX-1>=0:
            if cost[posX-1][posY]<0 and S[posX-1][posY]==".":
                cost[posX-1][posY] = cost[posX][posY]
                queue.append([posX-1,posY])
        if posY-1>=0:
            if cost[posX][posY-1]<0 and S[posX][posY-1]==".":
                cost[posX][posY-1] = cost[posX][posY]
                queue.append([posX,posY-1]) 
    #print(queue2)
    for a in range(len(queue2)):
            i=queue2[a][0]
            j=queue2[a][1]
            if cost[i][j]>=0:
                for k in range(-2,3):
                    for l in range(-2,3):
                        y, x = i+k, j+l
                        if x>0 and y>0 and x<W and y<H:
                            if cost[x][y]<0 and S[x][y]==".":
                                cost[x][y] = costCount
                                queue.append([x,y])
    costCount+=1
#print(cost)
print(cost[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)

    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        if nexts:
            for ne in nexts:
                dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)


    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)


    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)

    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(100000)
    
    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())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j, q):
        if vis[i][j]:
            return []
        vis[i][j] = True
        q.append((i, j))

        for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                continue
            if m[i + s][j + t] == '#':
                continue
            tmp = walk(i + s, j + t, q)

        return q

    def jump(i, j, c):
        tmp = walk(i, j, [])
        if (dh, dw) in tmp:
            return c
        res = []
        for s in range(-2, 3):
            for t in range(-2, 3):
                if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                    continue
                if (i + s, j + t) in tmp:
                    continue
                if m[i + s][j + t] == '#':
                    continue

                res += walk(i + s, j + t, [])
        if (dh, dw) in res:
            return c + 1
        else:
            for i, j in res:
                tmp = jump(i, j, c + 1)
                if tmp is not None:
                    return tmp

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque

    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())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j, q):
        if vis[i][j]:
            return []
        vis[i][j] = True
        q.append((i, j))

        for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                continue
            if m[i + s][j + t] == '#':
                continue
            tmp = walk(i + s, j + t, q)

        return q

    def jump(i, j, c):
        tmp = walk(i, j, [])
        if (dh, dw) in tmp:
            return c
        res = []
        for s in range(-2, 3):
            for t in range(-2, 3):
                if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                    continue
                if (i + s, j + t) in tmp:
                    continue
                if m[i + s][j + t] == '#':
                    continue

                res += walk(i + s, j + t, [])
        if (dh, dw) in res:
            return c + 1
        else:
            for i, j in res:
                tmp = jump(i, j, c + 1)
                if tmp is not None:
                    return tmp

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
mp = [None]+[[None]+[c for c in input()] for _ in range(h)]

mp[ch][cw]=0

from numba import jit

@njit
def mass11(_h, _w):
    l = []
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        side_h, side_w = _h+i, _w+j
        if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
            l.append((side_h, side_w))
    return l 

@njit
def mass55(_h, _w):
    l = []
    for i in range(5):
        for j in range(5):
            side_h, side_w = _h+i-2, _w+j-2
            if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
                l.append((side_h, side_w))
    return l 

@njit
def main():
    d = [(ch,cw)]
    while not len(d) == 0:
        _h, _w = d[0]
        d = d[1:]
        center_point = mp[_h][_w]
        # print(_h, _w)
        for side_h, side_w in mass11(_h, _w):
            side = mp[side_h][side_w]
            # print('side',side_h, side_w,side)
            if not side == '#' and not side == mp[_h][_w]:
                mp[side_h][side_w]=center_point
                d = [(side_h, side_w)] + d
        for side_h, side_w in mass55(_h, _w):
            if mp[side_h][side_w] == '.':
                mp[side_h][side_w]=center_point+1
                d.append((side_h, side_w))

    if mp[dh][dw] =='.':
        print(-1)
    else:
        print(mp[dh][dw])


main()

Submission status: Runtime Error

Solution code:
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        flag = False
        nexts = []
        curg = maze[cur_coor[0]][cur_coor[1]]
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne)
        if flag:
            dfs2(cur_coor)

    def dfs2(cur_coor):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cur_coor[0]][cur_coor[1]]
        for j1 in range(20):
            nexty2 = cur_coor[0] + warpy[j1]
            nextx2 = cur_coor[1] + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1((nexty2, nextx2))
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1((nexty2, nextx2))

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0

    dx_dys = [ [-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] ]

    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):
            """
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
            """
            for dx_dy in dx_dys:
                dx, dy = dx_dy[0], dx_dy[1]
                next = [x+ dx, y+ dy]
                if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                    dists[next[1] ][next[0] ] = dists[y][x]+1
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0
            
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1),(0,0)]
b = [-2,-1,0,1,2]
while True:
  flag = True
  # 行けるところすべて追加
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in a:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (Dh,Dw) == _p:
          print(ans)
          exit()
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          if not(i == 0 and j == 0):
            flag = True
  # クリアしてるか確認
  temps = set(d)
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in b:
        for j in b:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1