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:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
magic = [[-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]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Submission status: Time Limit Exceeded

Solution code:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-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]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j * \
                            k == 0 and abs(j) != 2 and abs(k) != 2 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


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

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def main():
    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
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    dist = visited[Dh][Dw]

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


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

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


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

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [sys.stdin.readline().strip() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            return visited[Dh][Dw]
        for j in range(-1, 2):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-1, 2):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x]
                            queue.appendleft([new_y, new_x])
        for j in range(-2, 3):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-2, 3):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j**2 + k**2 != 1 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x] + 1
                            queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        for j in range(-2, 3):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-2, 3):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j * \
                                k == 0 and abs(j) != 2 and abs(k) != 2 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x]
                            queue.appendleft([new_y, new_x])
                        elif maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x] + 1
                            queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

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

# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        # next_  = [
        #     (h[0] + 1, h[1], 0),
        #     (h[0] - 1, h[1], 0),
        #     (h[0], h[1] + 1, 0),
        #     (h[0], h[1] - 1, 0),]
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if 0 <= n[0] < H and 0 <= n[1] < W and S[n[0]][n[1]] == '.' and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if 0 <= n[0] < H and 0 <= n[1] < W and S[n[0]][n[1]] == '.' and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)