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(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 = []
    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(lambda x: int(x)+1, input().split())
goal_h, goal_w = map(lambda x: int(x)+1, input().split())

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

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]
        if used_map[n] > -1 and used_map[n] <= tl:
            continue
        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
                if abs(x)+abs(y) <= 1:
                    heapq.heappush(queue,[tl,(th+x)*w+tw+y])
                else:
                    heapq.heappush(queue,[tl+1,(th+x)*w+tw+y])

    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]
        if used_map[n] > -1 and used_map[n] <= tl:
            continue
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w or road_map[th+x][tw+y] == True):
                    if x == y == 0:
                        continue
                    if abs(x)+abs(y) <= 1:
                        heapq.heappush(queue,[tl,(th+x)*w+tw+y])
                    else:
                        heapq.heappush(queue,[tl+1,(th+x)*w+tw+y])

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

    INF = height * width + 1
    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 = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                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 arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


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

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

    INF = 10 ** 7
    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))
    qu_append = qu.append
    qu_popleft = qu.popleft
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        arrived_set_by_cost_add = arrived_set_by_cost.add
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu_popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost_add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu_append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                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 arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu_append((new_h, new_w))
    return arrived[dest_h][dest_w]


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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)
            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)
        next = set()
        while que:
            now = que.popleft()
            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 = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

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))
    qu_append = qu.append
    qu_popleft = qu.popleft
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        arrived_set_by_cost_add = arrived_set_by_cost.add
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu_popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost_add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                qu_append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                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 grid[new_h][new_w] == '#':
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                qu_append((new_h, new_w))
    return arrived[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)
        if used_map[n] > -1 and used_map[n] <= tl:
            continue

        used_map[n] = tl

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

    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:
# list(map(int, input().split()))
# int(input())
from collections import deque

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 = {tuple(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)
            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)
        next = set()
        while que:
            now = que.popleft()
            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)
            {next.add(canmove) for canmove in make_st(*now) if moverange(*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 = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

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 = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                qu.append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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 = {tuple(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)
            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)
        next = set()
        while que:
            now = que.popleft()
            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 = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, goal):
    H = len(MAZE)
    W = len(MAZE[0])
    MAP = [[INF] * W for _ in range(H)]
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = deque([])
    k = (0,) + start
    queue.append(k)

    while queue:
        count, ci, cj = queue.pop()
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count:
                queue.append((count, ni, nj))
                MAP[ni][nj] = count
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count+1:
                queue.appendleft((count+1, ni, nj))
                MAP[ni][nj] = count + 1
    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    for i in range(H):
        s = input()
        s = '##' + s + '##'
        MAZE.append(s)
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, goal):
    H = len(MAZE)
    W = len(MAZE[0])
    MAP = [[INF] * W for _ in range(H)]
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = deque([])
    k = (0,) + start
    queue.append(k)

    while queue:
        count, ci, cj = queue.pop()
        MAP[ci][cj] = count
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count:
                queue.append((count, ni, nj))
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count+1:
                queue.appendleft((count+1, ni, nj))
    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    for i in range(H):
        s = input()
        s = '##' + s + '##'
        MAZE.append(s)
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))





if __name__ == "__main__":
    run()

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)]
    INF = 10 ** 3

    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 = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for adj_h, adj_w in adjacents:
                candidate_h, candidate_w = now_h + adj_h, now_w + adj_w
                if candidate_h < 0 or candidate_h >= height:
                    continue
                if candidate_w < 0 or candidate_w >= width:
                    continue
                if arrived[candidate_h][candidate_w] != -1:
                    continue
                if grid[candidate_h][candidate_w] == '#':
                    arrived[candidate_h][candidate_w] = INF
                    continue
                qu.append((candidate_h, candidate_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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 = {tuple(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)
            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 masu[D[0]][D[1]] == -1 and len(next) != 0:
        kaisu += 1
        que = deque(next)
        next = set()
        while que:
            now = que.popleft()
            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 = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)