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: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    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=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(i8(b1[:,:],i8,i8,i8,i8),cache=True)
def solve(road_map,ch,cw,dh,dw):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    max_l = 2<<30
    used_map = np.full(h*w,max_l,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        tl,n = heapq.heappop(queue)
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    heapq.heappush(queue,(loop,next_n))

    ans = used_map[goal]
    if ans == max_l:
        return -1
    else:
        return ans

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(road_map,ch,cw,dh,dw))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    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=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    max_l = 2<<30
    used_map = np.full(h*w,max_l,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        tl,n = heapq.heappop(queue)
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    heapq.heappush(queue,(loop,next_n))

    if used_map[goal] == max_l:
        return -1
    else:
        return used_map[goal]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    used_map = np.full(h*w,2<<30,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    heapq.heappush(queue,(loop,next_n))

    if used_map[goal] == 2<<30:
        return -1
    else:
        return used_map[goal]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))

Submission status: Time Limit Exceeded

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

    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 S[x][y] == '.'

    def func(now, kaisu):
        x, y = now
        for canmove in {(x-1, y), (x+1, y), (x, y+1), (x, y-1)}:
            if moverange(*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)
    print(masu[D[0]][D[1]])


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [(0,ch*w+cw)]
    used_map = np.full(h*w,-1,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,(loop,next_n))

    return used_map[dh*w+dw]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))

Submission status: Time Limit Exceeded

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):
        x, y = now
        for canmove in {(x-1, y), (x+1, y), (x, y+1), (x, y-1)}:
            if moverange(*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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    return used_map[dh*w+dw]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))

Submission status: Time Limit Exceeded

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 up(x, y):
        return (x-1, y)

    def down(x, y):
        return (x+1, y)

    def right(x, y):
        return (x, y+1)

    def left(x, y):
        return (x, y-1)

    # def func(now, direction, kaisu):
    #     canmove = direction(*now)
    #     if moverange(*canmove):
    #         # que.append(canmove)
    #         que.add(canmove)
    #         masu[canmove[0]][canmove[1]] = kaisu

    def func(now, kaisu):
        for canmove in map(lambda x:x(*now), [up, down, right, left]):
            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 = deque(next)
        que = next
        next = set()
        while que:
            # now = que.popleft()
            now = que.pop()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            # func(now, up, kaisu)
            # func(now, down, kaisu)
            # func(now, right, kaisu)
            # func(now, left, 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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())

array_st=list(map(int,input().split()))
array_gl=list(map(int,input().split()))
start_point=[]
goal_point=[]
for i in range(2):
    start_point.append(array_st[i]-1)
    goal_point.append(array_gl[i]-1)

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

d=deque()
d.append([start_point[0],start_point[1],0])

road=[-1,1]

ans=-1
while d:
    v=d.popleft()
    matrix[v[0]][v[1]]="x"
    if [v[0],v[1]]==goal_point:
        ans=v[2]
        break
    for i in road:
        if v[0]+i>=0 and v[0]+i<H:
            if matrix[v[0]+i][v[1]]==".":
                d.appendleft([v[0]+i,v[1],v[2]])
        if v[1]+i>=0 and v[1]+i<W:
            if matrix[v[0]][v[1]+i]==".":
                d.appendleft([v[0],v[1]+i,v[2]])

    for i in range(-2,3):
        for j in range(-2,3):
            if v[0]+i>=0 and v[0]+i<H:
                if v[1]+j>=0 and v[1]+j<W:
                    if matrix[v[0]+i][v[1]+j]==".":
                        d.append([v[0]+i,v[1]+j,v[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)

    #move walk
            
    while used_map[dh*w+dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)

    #move walk
    while used_map[dh*w+dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w or road_map[th+x][tw+y] == True:
                    continue
                if x == y == 0:
                    continue
                next_n  = (th+x)*w+tw+y
                check = used_map[next_n]
                if check == -1 or check > tl:
                    if abs(x)+abs(y) <= 1:
                        heapq.heappush(queue,[tl,next_n])
                if check == -1 or check > tl+1:
                    heapq.heappush(queue,[tl+1,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

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 up(x, y):
        return (x-1, y)

    def down(x, y):
        return (x+1, y)

    def right(x, y):
        return (x, y+1)

    def left(x, y):
        return (x, y-1)

    def func(now, direction, kaisu):
        canmove = direction(*now)
        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 = deque(next)
        que = next
        next = set()
        while que:
            # now = que.popleft()
            now = que.pop()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            func(now, up, kaisu)
            func(now, down, kaisu)
            func(now, right, kaisu)
            func(now, left, 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)]
    # S = []
    # for _ in range(H):
    #     S.append(input())
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
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[start_h][start_w] = 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, 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)]

yet = deque([(start_h, start_w)])
done = deque()

while len(yet) > 0:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: #"."でまだ辿り着いていないマス
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while len(done) > 0:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)

    #move walk
    while used_map[dh*w+dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w or road_map[th+x][tw+y] == True:
                    continue
                if x == y == 0:
                    continue
                next_n  = (th+x)*w+tw+y
                if used_map[next_n] == -1 or used_map[next_n] > tl:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[tl,next_n])
                        else:
                            heapq.heappush(queue,[tl+1,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
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[start_h][start_w] = 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, 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)]

yet = deque([(start_h, start_w)])
done = deque()

while yet:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: 
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while done:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])