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 queue
    import sys
    input = sys.stdin.readline

    H, W = list(map(int, input().split()))
    S = list(map(int, input().split()))
    G = list(map(int, input().split()))
    S = [S[0] - 1, S[1] - 1]
    G = [G[0] - 1, G[1] - 1]

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

    MAX = 1000001
    cost_list = [[MAX] * W for i in range(H)]


    to_walk = queue.Queue()
    to_warp = queue.Queue()


    def walk(z):
        h, w = z
        cost = cost_list[h][w]
        to_warp.put([h, w])
        for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            a,b=h+p,w+q
            if (0 <= a < H) and (0 <= b < W):
                if maze[a][b] == "." and cost_list[a][b] > cost:
                    cost_list[a][b] = cost
                    to_walk.put([a,b])
                    to_warp.put([a,b])


    def warp(z):
        h, w = z
        cost = cost_list[h][w] + 1
        for [p, q] in [[-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]]:
            a,b=h+p,w+q
            if (0 <= a < H) and (0 <= b < W):
                if maze[a][b] == "." and cost_list[a][b] > cost:
                    cost_list[a][b] = cost
                    to_walk.put([a, b])


    to_walk.put(S)
    cost_list[S[0]][S[1]] = 0

    while True:
        while not to_walk.empty():
            walk(to_walk.get())
        while not to_warp.empty():
            warp(to_warp.get())
        if to_walk.empty() and to_warp.empty():
            break

    if cost_list[G[0]][G[1]] == MAX:
        print(-1)
    else:
        print(cost_list[G[0]][G[1]])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    to_warp.put([h, w])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        a,b=h+p,w+q
        if (0 <= a < H) and (0 <= b < W):
            if maze[a][b] == "." and cost_list[a][b] > cost:
                cost_list[a][b] = cost
                to_walk.put([a,b])
                to_warp.put([a,b])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in [[-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]]:
        a,b=h+p,w+q
        if (0 <= a < H) and (0 <= b < W):
            if maze[a][b] == "." and cost_list[a][b] > cost:
                cost_list[a][b] = cost
                to_walk.put([a, b])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    to_warp.put([h, w])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])
                to_warp.put([h + p, w + q])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in [[-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]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[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 _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.popleft()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.appendleft([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.appendleft([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])

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 _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.pop()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.append([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.append([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import pprint
import time
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

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

for i in range(h):
    for j in range(w):
        if C[i][j] == '#':
            dist[i][j] = -2

def solve():
    queue = []
    queue.append([sh,sw])
    dist[sh][sw] = 0
    check_list = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        check_list.append([x,y])
        for p, q in move:
            nx = x + p
            ny = y + q
            if 0 <= nx < h and 0 <= ny < w and dist[nx][ny] == -1:
                queue.append([nx,ny])
                dist[nx][ny] = dist[x][y]
                check_list.append([nx,ny])
                if [nx, ny] == [gh, gw]:
                    return True
        
        if len(queue) == 0:
            while len(check_list) > 0:
                x2, y2 = check_list.pop(0) 
                for p2, q2 in magic:
                    nx2 = x2 + p2
                    ny2 = y2 + q2
                    if 0 <= nx2 < h and 0 <= ny2 < w and dist[nx2][ny2] == -1:
                        dist[nx2][ny2] = dist[x2][y2]+1
                        queue.append([nx2, ny2])

solve()
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import pprint
import time
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

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

for i in range(h):
    for j in range(w):
        if C[i][j] == '#':
            dist[i][j] = -2

def solve():
    queue = []
    queue.append([sh,sw])
    dist[sh][sw] = 0
    check_list = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        check_list.append([x,y])
        for p, q in move:
            nx = x + p
            ny = y + q
            if 0 <= nx < h and 0 <= ny < w and dist[nx][ny] == -1:
                queue.append([nx,ny])
                dist[nx][ny] = dist[x][y]
                check_list.append([nx,ny])
        
        if len(queue) == 0:
            while len(check_list) > 0:
                x2, y2 = check_list.pop(0) 
                for p2, q2 in magic:
                    nx2 = x2 + p2
                    ny2 = y2 + q2
                    if 0 <= nx2 < h and 0 <= ny2 < w and dist[nx2][ny2] == -1:
                        dist[nx2][ny2] = dist[x2][y2]+1
                        queue.append([nx2, ny2])

solve()
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from itertools import product
    # print()
    H, W = [int(x) for x in input().split(" ")]

    Cy, Cx = [int(x) - 1 for x in input().split(" ")]
    Gy, Gx = [int(x) - 1 for x in input().split(" ")]
    M = []
    for i in range(H):
        r = list(input())
        M.append(r)
    # show_map(M)
    # print(f"{(Gx, Gy)}")

    def get_new(_current_pos, _move, _map):
        _pos = []
        for m in _move:
            x = _current_pos[0] + m[0]
            y = _current_pos[1] + m[1]
            if (0 <= x < W) and (0 <= y < H) and ((x, y) not in _pos):
                if _map[y][x] == ".":
                    _pos.append((x, y))
        return _pos

    def get_2(_checked):
        _pos = []
        _move = [x for x in list(product(list(range(-2, 3)), list(range(-2, 3)))) if x not in [(1, 0), (-1, 0), (0, 1), (0, -1), (0, 0)]]
        for p in _checked:
            for _p in get_new(p, _move, M):
                if _p not in _checked:
                    _pos.append(_p)

        return _pos

    def normal_move(_queue, _checked):
        while _queue:
            _pos = _queue.pop(0)
            _c = M[_pos[1]][_pos[0]]
            # print(f"{_pos}: {_c}   ,{_queue}")
            if _c == "#":
                continue
            if _pos[0] == Gx and _pos[1] == Gy:
                _checked.append(_pos)
                return True, _checked
            if _pos in _checked:
                continue

            _checked.append(_pos)

            for p in get_new(_pos, [(1, 0), (-1, 0), (0, 1), (0, -1)], M):
                if p not in _queue:
                    _queue.append(p)

        return False, _checked

    magic = 0
    q = [(Cx, Cy)]
    checked = []
    found = False
    while q:
        found, checked = normal_move(q, checked)
        if (Gx, Gy) in checked:
            found = True
            break
        else:
            for _p in get_2(checked):
                q.append(_p)
            # print(f"[{magic}] \n {checked} \n {get_2(checked)}")
            magic += 1
    if not found:
        magic = -1
    print(magic)

resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 10:54:09 2020

@author: Kozu
"""
from collections import deque
import numpy as np    
from sys import stdin

#標準入力
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H-1):
  S.append(list(stdin.readline()[:-1]))
S.append(list(stdin.readline()))

#定数
Wall = -1
WildArea = 1e9
#変数
T = np.full([H + 4,W + 4],Wall)
t = 0
Deque = deque()
#右上左下
dx = [1,0,-1,0]
dy = [0,1,0,-1]


#初期処理
for i in range(2):
    C[i] -= 1
    D[i] -= 1
    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i + 2][j + 2] = Wall
        if S[i][j] == '.':
            T[i + 2][j + 2] = WildArea


T[C[0] + 2][C[1] + 2] = 0
Deque.append([C[0] + 2,C[1] + 2])

while True:
    n = Deque.pop()
    
    t = T[n[0]][n[1]]
    
    #BFS 幅優先探索
    for i in range(4):
        if T[n[0] + dx[i]][n[1] + dy[i]] == Wall:
            continue
        if T[n[0] + dx[i]][n[1] + dy[i]] <= t:
            continue
        
        T[n[0] + dx[i]][n[1] + dy[i]] = t
        Deque.append([n[0] + dx[i],n[1] + dy[i]])
    
    #Warp　ワープ
    for i in range(-2,3):
        for j in range(-2,3):
            if T[n[0]+ i][n[1] + j] == Wall:
                continue
            if T[n[0]+ i][n[1] + j] <= t + 1:
                continue
            T[n[0]+ i][n[1] + j] = t + 1
            Deque.appendleft([n[0]+ i,n[1] + j])            

    if len(Deque) <= 0:
        break;

            
            
ans = T[D[0] + 2][D[1] + 2]
if ans == WildArea:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 10:54:09 2020

@author: Kozu
"""
from collections import deque
import numpy as np    

#標準入力
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H):    
  S.append(list(input()))
  
#定数
Wall = -1
WildArea = 1e9
#変数
T = np.full([H + 4,W + 4],Wall)
t = 0
Deque = deque()
#右上左下
dx = [1,0,-1,0]
dy = [0,1,0,-1]


#初期処理
for i in range(2):
    C[i] -= 1
    D[i] -= 1
    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i + 2][j + 2] = Wall
        if S[i][j] == '.':
            T[i + 2][j + 2] = WildArea


T[C[0] + 2][C[1] + 2] = 0
Deque.append([C[0] + 2,C[1] + 2])

while True:
    n = Deque.pop()
    
    t = T[n[0]][n[1]]
    
    #BFS 幅優先探索
    for i in range(4):
        if T[n[0] + dx[i]][n[1] + dy[i]] == Wall:
            continue
        if T[n[0] + dx[i]][n[1] + dy[i]] <= t:
            continue
        
        T[n[0] + dx[i]][n[1] + dy[i]] = t
        Deque.append([n[0] + dx[i],n[1] + dy[i]])
    
    #Warp　ワープ
    for i in range(-2,3):
        for j in range(-2,3):          
            if T[n[0]+ i][n[1] + j] == Wall:
                continue
            if T[n[0]+ i][n[1] + j] <= t + 1:
                continue
            T[n[0]+ i][n[1] + j] = t + 1
            Deque.appendleft([n[0]+ i,n[1] + j])            

    if len(Deque) <= 0:
        break;

            
            
ans = T[D[0] + 2][D[1] + 2]
if ans == WildArea:
    ans = -1
print(ans)
#print(T)

"""
20 10
10 10
19 8
.#.#.#.#.#
..........
##########
..##..##..
##.####.##
..........
##########
.#..#..#.#
#..#..#..#
##.....#..
######.###
.....#....
##########
..########
..#.#.#.#.
##########
#########.
..........
#######.##
..........
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main() :
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [[c for c in input()] for _ in range(H)]
    check = [[-1] * W for _ in range(H)]    # -1は未訪問の印
    check[D[0] - 1][D[1] - 1] = -2          # -2は目的地の印
    f = -1                                  # 到達の判定
    n = 0                                   # move_bの使用回数
    que = deque()
    que2 = deque()
    que.append([C[0] -1, C[1] -1])

    while que:
        while que:
            cp = que.pop()                     # current_place
            check[cp[0]][cp[1]] = n            # n(0,1,2,...)は既訪問の印
            que2.append([cp[0], cp[1]])
            for move_a_x, move_a_y in [[1,0], [-1,0], [0,1], [0,-1]]:   # move_aの４種の動き
                x = cp[0] + move_a_x
                y = cp[1] + move_a_y
                if not 0 <= x < H : continue
                if not 0 <= y < W : continue
                if check[x][y] == -1 and S[x][y] == '.':
                    check[x][y] = -3        # -3は移動候補の印
                    que.append([x, y])
                elif check[x][y] == -2: 
                    f = n
                    check[x][y] = -4       # ゴールに到達したら-4にする

        n += 1
        while que2:
            cp = que2.pop()
            #move_b
            for move_b_x in range(-2, 3):
                for move_b_y in range(-2, 3):
                    x = cp[0] + move_b_x
                    y = cp[1] + move_b_y
                    if x >= 0 and x < H and y >= 0 and y < W:
                        if check[x][y] == -2:
                            f=n
                            check[x][y] == -4
                        if S[x][y]=='.' and check[x][y] == -1:
                            que.append([x, y])
    print(f)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main() :
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [[c for c in input()] for _ in range(H)]
    check = [[-1] * W for _ in range(H)]    # -1は未訪問の印
    check[D[0] - 1][D[1] - 1] = -2          # -2は目的地の印
    f = -1                                  # 到達の判定
    n = 0                                   # move_bの使用回数
    que = deque()
    que2 = deque()
    que.append([C[0] -1, C[1] -1])

    while(que):
        while(que):
            cp = que.pop()                     # current_place
            check[cp[0]][cp[1]] = n            # n(0,1,2,...)は既訪問の印
            que2.append([cp[0], cp[1]])
            for move_a in [[1,0], [-1,0], [0,1], [0,-1]]:   #move_aの４種の動き
                x = cp[0] + move_a[0]
                y = cp[1] + move_a[1]
                if x >= 0 and x < H and y >= 0 and y < W:
                    if check[x][y] == -2: 
                        f = n
                        check[x][y] = -4       # ゴールに到達したら-4にする
                    if check[x][y] == -1 and S[x][y] == '.':
                        check[x][y] = -3        # -3は移動候補の印
                        que.append([x, y])

        n += 1
        while(que2):
            cp = que2.pop()
            #move_b
            for move_b_x in range(-2, 3):
                for move_b_y in range(-2, 3):
                    x = cp[0] + move_b_x
                    y = cp[1] + move_b_y
                    if x >= 0 and x < H and y >= 0 and y < W:
                        if check[x][y] == -2:
                            f=n
                            check[x][y] == -4
                        if S[x][y]=='.' and check[x][y] == -1:
                            que.append([x, y])
    print(f)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main() :
    H, W =list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [[c for c in input()] for _ in range(H)]
    check = [[-1] * W for _ in range(H)]    # -1は未訪問の印
    check[D[0] - 1][D[1] - 1] = -2          # -2は目的地の印
    f = -1                                  # 到達の判定
    n = 0                                   # move_bの使用回数
    que = deque()
    que.append([C[0] -1, C[1] -1])

    while(que):
        while(que):
            cp = que.pop()                     # current_place
            check[cp[0]][cp[1]] = n            # n(0,1,2,...)は既訪問の印
            for move_a in [[1,0], [-1,0], [0,1], [0,-1]]:   #move_aの４種の動き
                x = cp[0] + move_a[0]
                y = cp[1] + move_a[1]
                if x >= 0 and x < H and y >= 0 and y < W:
                    if check[x][y] == -2: 
                        f = n
                        check[x][y] = -4
                    if check[x][y] == -1 and S[x][y] == '.':
                        check[x][y] = -3        # -3は移動候補の印
                        que.append([x, y])

        n += 1
        for i in range(H):
            for j in range(W):
                if check[i][j] == n - 1:
                    #move_b
                    for i2 in range(-2, 3):
                        for j2 in range(-2, 3):
                            x = i+i2
                            y = j+j2
                            if x >= 0 and x < H and y >= 0 and y < W:
                                if check[x][y] == -2:
                                    f=n
                                    check[x][y] == -4
                                if S[x][y]=='.' and check[x][y] == -1:
                                    que.append([x, y])
    print(f)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

inf = 10 ** 10
cost = [[inf] * w for _ in range(h)]

walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if [i, j] not in [[0, 0]] + walk]

q = deque()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-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)]

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
INF=1000000000
cnt = [[INF]*(w+4) for i in range(h+4)]
ch+=1; cw+=1; dh+=1; dw+=1

def bfs7():
    '''
    collections.dequeを使う
    mを書き換えない ,cntを使う
    '''
    Q=deque()
    cnt[ch][cw]=0
    Q.append((ch,cw))

    while Q:
        i,j=Q.popleft() 
        for si,sj in ad:
            if m[i+si][j+sj]=='.' and cnt[i][j]<cnt[i+si][j+sj]:# and cnt[i+si][j+sj]==-1はいらないはず
                cnt[i+si][j+sj]=cnt[i][j]
                Q.appendleft((i+si,j+sj))

        for si,sj in warp:
            if m[i+si][j+sj]=='.' and cnt[i][j]+1<cnt[i+si][j+sj]:
                cnt[i+si][j+sj]=cnt[i][j]+1
                Q.append((i+si, j+sj))
                
bfs7()

if cnt[dh][dw] == INF:
    print(-1)
else:
    print(cnt[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())

f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
from sys import stdin
input=stdin.readline
l=[input() for _ in range(h)]
cost=[[0]*w for _ in range(h)]
visit=[[c1,c2]]

l1=[[c1,c2]]
l2=[]
walk=[[1,0],[-1,0],[0,1],[0,-1]]
wap=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
cost[d1][d2]=-1

roop=1
while len(l1)>0:
  x,y=l1.pop(0)
  l2.append([x,y])
  for a,b in walk:
    xx=x+a
    yy=y+b
    if 0<=xx<h and 0<=yy<w and l[xx][yy]!='#' and [xx,yy] not in visit:
      cost[xx][yy]=cost[x][y]
      visit.append([xx,yy])
      l1.append([xx,yy])
      l2.append([xx,yy])
  if len(l1)==0:
    while len(l2)>0:
      s,t=l2.pop(0)
      for p,q in wap:
        pp=s+p
        qq=t+q
        if 0<=pp<h and 0<=qq<w and l[pp][qq]!='#' and [pp,qq] not in visit:
          cost[pp][qq]=cost[s][t]+1
          visit.append([pp,qq])
          l1.append([pp,qq])
print(cost[d1][d2])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())

f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
l=[input() for _ in range(h)]
cost=[[0]*w for _ in range(h)]
visit=[[c1,c2]]

l1=[[c1,c2]]
l2=[]
walk=[[1,0],[-1,0],[0,1],[0,-1]]
wap=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
cost[d1][d2]=-1

roop=1
while len(l1)>0:
  x,y=l1.pop(0)
  l2.append([x,y])
  for a,b in walk:
    xx=x+a
    yy=y+b
    if 0<=xx<h and 0<=yy<w and l[xx][yy]!='#' and [xx,yy] not in visit:
      cost[xx][yy]=cost[x][y]
      visit.append([xx,yy])
      l1.append([xx,yy])
      l2.append([xx,yy])
  if len(l1)==0:
    while len(l2)>0:
      s,t=l2.pop(0)
      for p,q in wap:
        pp=s+p
        qq=t+q
        if 0<=pp<h and 0<=qq<w and l[pp][qq]!='#' and [pp,qq] not in visit:
          cost[pp][qq]=cost[s][t]+1
          visit.append([pp,qq])
          l1.append([pp,qq])
print(cost[d1][d2])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
import sys
sys.setrecursionlimit(1000000)
f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
l=[input() for _ in range(h)]
cost=[[0]*w for _ in range(h)]
visit=[[c1,c2]]
from collections import deque
l1=[[c1,c2]]
l2=[]
walk=[[1,0],[-1,0],[0,1],[0,-1]]
wap=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
cost[d1][d2]=-1

roop=1
while len(l1)>0:
  x,y=l1.pop(0)
  l2.append([x,y])
  for a,b in walk:
    xx=x+a
    yy=y+b
    if 0<=xx<h and 0<=yy<w and l[xx][yy]!='#' and [xx,yy] not in visit:
      cost[xx][yy]=cost[x][y]
      visit.append([xx,yy])
      l1.append([xx,yy])
      l2.append([xx,yy])
  if len(l1)==0:
    while len(l2)>0:
      s,t=l2.pop(0)
      for p,q in wap:
        pp=s+p
        qq=t+q
        if 0<=pp<h and 0<=qq<w and l[pp][qq]!='#' and [pp,qq] not in visit:
          cost[pp][qq]=cost[s][t]+1
          visit.append([pp,qq])
          l1.append([pp,qq])
print(cost[d1][d2])

Submission status: Time Limit Exceeded

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

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []
queue1 = [[1,0],[-1,0],[0,1],[0,-1]]
queue2 = [
        [-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]
    ]

def nowRange(now):
    r = []
    for i in queue1:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j > -1 and W > k > -1:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) != 0:
        return r + stepRange(r)
    else:
        return []


def nowWarp(now):
    r = []
    for i in queue2:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j > -1 and W > k > -1:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
            
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) != 0:
        return r
    else:
        print(-1)
        exit()


while True:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)