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:
from collections import deque

INF = 10**6

H,W = map(int,input().split())
C1,C2 =map(lambda x : int(x) - 1,input().split())
D1,D2 = map(lambda x : int(x) - 1,input().split())

S = [input() for _ in range (H)]
t = [[INF]*W for _ in range (H)]


for h in range (H):
    Sh = S[h]
    th = t[h]
    for w in range (W):
        if Sh[w] == '#':
            th[w] = -1


q = deque([(C1,C2)])
a = 0
t[C1][C2] = a

while q:
    warpq = []
    while q:
        h,w = q.popleft()
        warpq.append((h,w))
        if 0 < h and t[h-1][w] > a:
            t[h-1][w] = a
            q.append((h-1,w))
        if H-1 > h and t[h+1][w] > a:
            t[h+1][w] = a
            q.append((h+1,w))
        if 0 < w and t[h][w-1] > a:
            t[h][w-1] = a
            q.append((h,w-1))
        if w < W-1 and t[h][w+1] > a:
            t[h][w+1] = a
            q.append((h,w+1))

    if t[D1][D2]!= INF:
        break

    a+=1

    for h,w in warpq:
        for i in range (max(0,h-2),min(H,h+3)):
            ti = t[i]
            for j in range (max(0,w-2),min(W,w+3)):
                if ti[j] >a:
                    ti[j] = a
                    q.append((i,j))


if t[D1][D2] == INF:
    print(-1)
else:
    print(t[D1][D2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = [LARGEST] * W
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if index > status[hIndex][wIndex]:
            continue

        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '#':
                continue

            tmpIndex = index
            if status[sH][sW] > tmpIndex:
                status[sH][sW] = tmpIndex
                q.append((sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '#':
                    continue

                tmpIndex = index + 1

                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(status[d0][d1])


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])

def bfs(pnxt):
    next_q = deque([])
    for hw in pnxt:
        next_q.append(hw)
    nxt = set([])
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1


    status = np.empty((h,w))
    status[:][:] = LARGEST

    status[c0][c1] = 0
    q = deque()

    q.append((c0, c1))

    while len(q) > 0:
        hIndex, wIndex = q.popleft()


        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '#':
                continue

            if status[sH][sW] > status[hIndex][wIndex]:
                status[sH][sW] = status[hIndex][wIndex]
                q.insert(0, (sH, sW))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '#':
                    continue

                tmpIndex = status[hIndex][wIndex]+1
                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(int(status[d0][d1]))


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**6

H,W = map(int,input().split())
C1,C2 =map(lambda x : int(x) - 1,input().split())
D1,D2 = map(lambda x : int(x) - 1,input().split())

S = [input() for _ in range (H)]
t = [[INF]*W for _ in range (H)]


for h in range (H):
    for w in range (W):
        if S[h][w] == '#':
            t[h][w] = -1


q = deque([(C1,C2)])
a = 0
t[C1][C2] = a

while q:
    warpq = []
    while q:
        h,w = q.popleft()
        warpq.append((h,w))
        if 0 < h and t[h-1][w] > a:
            t[h-1][w] = a
            q.append((h-1,w))
        if H-1 > h and t[h+1][w] > a:
            t[h+1][w] = a
            q.append((h+1,w))
        if 0 < w and t[h][w-1] > a:
            t[h][w-1] = a
            q.append((h,w-1))
        if w < W-1 and t[h][w+1] > a:
            t[h][w+1] = a
            q.append((h,w+1))

    if t[D1][D2]!= INF:
        break

    a+=1

    for h,w in warpq:
        for i in range (max(0,h-2),min(H,h+3)):
            for j in range (max(0,w-2),min(W,w+3)):
                if t[i][j] >a:
                    t[i][j] = a
                    q.append((i,j))


if t[D1][D2] == INF:
    print(-1)
else:
    print(t[D1][D2])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    warpy1 = (-2, -2, -1, -1, 0, 1, 1, 2, 2)
    warpx1 = ( 1,  2,  1,  2, 2, 1, 2, 1, 2)
    warpy2 = (-2, -2, -2, -2, -2, -1, -1, -1, -1)
    warpx2 = (-2, -1,  0,  1,  2, -2, -1,  1, 2)
    warpy3 = (-2, -2, -1, -1,  0,  1,  1,  2, 2)
    warpx3 = (-2, -1, -2, -1, -2, -2, -1, -2, -1)
    warpy4 = ( 1,  2,  1,  2,  2,  1,  1, 1, 2)
    warpx4 = (-2, -2, -1, -1,  0,  1,  2, 2, 2)
    warps = []
    warps.append((warpy1, warpx1))
    warps.append((warpy2, warpx2))
    warps.append((warpy3, warpx3))
    warps.append((warpy4, warpx4))
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    #maze[dh][dw] = 'g'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    #cnt = 0
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            curg = maze[nextny][nextnx]
            flag = False
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
                elif maze[ny][nx] == '#':
                    warpnext_y = warps[j1][0]
                    warpnext_x = warps[j1][1]
                    for k1 in range(9):
                        ny = nextny + warpnext_y[k1]
                        nx = nextnx + warpnext_x[k1]
                        nextg = maze[ny][nx]
                        if nextg == '.':
                            next2_nodes.append((ny, nx))
                            maze[ny][nx] = curg + 1
                        elif nextg == '#':
                            pass
                        elif nextg > curg + 1:
                            maze[ny][nx] = curg + 1
                            next2_nodes.append((ny, nx))
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))

        next_nodes = deque(set(deepcopy(next2_nodes)))
        next2_nodes = deque()
    g = maze[dh][dw]

    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    visited = set()
    while q:
        cnt, h, w = heappop(q)
        visited.add((h, w))
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                if h+i < 0 or w+j < 0: continue
                if h+i >= H or w+j >= W: continue
                if field[h+i][w+j]  == "#": continue
                if (h+i, w+j) in visited: continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    heappush(q, (cnt, h+i, w+j))
                else:
                    heappush(q, (cnt+1, h+i, w+j))
    return -1

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = [LARGEST] * W
        status.append(tmp)

    status[c0][c1] = 0
    q = deque()

    q.append((c0, c1))

    while len(q) > 0:
        hIndex, wIndex = q.popleft()


        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '#':
                continue

            if status[sH][sW] > status[hIndex][wIndex]:
                status[sH][sW] = status[hIndex][wIndex]
                q.insert(0, (sH, sW))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '#':
                    continue

                tmpIndex = status[hIndex][wIndex]+1
                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(status[d0][d1])


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    warpy1 = (-2, -2, -1, -1, 0, 1, 1, 2, 2)
    warpx1 = ( 1,  2,  1,  2, 2, 1, 2, 1, 2)
    warpy2 = (-2, -2, -2, -2, -2, -1, -1, -1, -1)
    warpx2 = (-2, -1,  0,  1,  2, -2, -1,  1, 2)
    warpy3 = (-2, -2, -1, -1,  0,  1,  1,  2, 2)
    warpx3 = (-2, -1, -2, -1, -2, -2, -1, -2, -1)
    warpy4 = ( 1,  2,  1,  2,  2,  1,  1, 1, 2)
    warpx4 = (-2, -2, -1, -1,  0,  1,  2, 2, 2)
    warps = []
    warps.append((warpy1, warpx1))
    warps.append((warpy2, warpx2))
    warps.append((warpy3, warpx3))
    warps.append((warpy4, warpx4))
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    #maze[dh][dw] = 'g'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    #cnt = 0
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            curg = maze[nextny][nextnx]
            flag = False
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
                elif maze[ny][nx] == '#':
                    warpnext_y = warps[j1][0]
                    warpnext_x = warps[j1][1]
                    for k1 in range(9):
                        ny = nextny + warpnext_y[k1]
                        nx = nextnx + warpnext_x[k1]
                        nextg = maze[ny][nx]
                        if nextg == '.':
                            next2_nodes.append((ny, nx))
                            maze[ny][nx] = curg + 1
                        elif nextg == '#':
                            pass
                        elif nextg > curg + 1:
                            maze[ny][nx] = curg + 1
                            next2_nodes.append((ny, nx))
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))

        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    g = maze[dh][dw]
    
    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=deque()

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)

while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            ttemp=start.popleft()
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=ttemp[0]+hh
                    nny=ttemp[1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[-1] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    move2 = [
        [-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]
    ]
    wark = collections.deque([[Ch - 1, Cw - 1]])
    warp = collections.deque([])

    visited[Ch - 1][Cw - 1] = 0
    while wark:
        h, w = wark.popleft()
        warp.append((h, w))
        for mh, mw in move:
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                visited[ch][cw] = visited[h][w]
                wark.append([ch, cw])
        if len(wark) == 0:
            while warp:
                h, w = warp.popleft()
                for wh, ww in move2:  # 移動B: ワープ魔法
                    ch, cw = h + wh, w + ww
                    if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                        visited[ch][cw] = visited[h][w] + 1
                        wark.append([ch, cw])

    ret = visited[Dh - 1][Dw - 1]
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[-1] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    wark = collections.deque([[Ch - 1, Cw - 1]])
    warp = collections.deque([])

    visited[Ch - 1][Cw - 1] = 0
    while wark:
        h, w = wark.popleft()
        warp.append((h, w))
        for mh, mw in move:
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                visited[ch][cw] = visited[h][w]
                wark.append([ch, cw])
        if len(wark) == 0:
            while warp:
                h, w = warp.popleft()
                for wh in range(-2, 3):  # 移動B: ワープ魔法
                    for ww in range(-2, 3):
                        ch, cw = h + wh, w + ww
                        if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                            visited[ch][cw] = visited[h][w] + 1
                            wark.append([ch, cw])

    ret = visited[Dh - 1][Dw - 1]
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = [LARGEST] * W
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if index > status[hIndex][wIndex]:
            continue

        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '#':
                continue

            tmpIndex = index
            if status[sH][sW] > tmpIndex:
                status[sH][sW] = tmpIndex
                q.insert(0, (sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '#':
                    continue

                tmpIndex = index + 1

                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(status[d0][d1])


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break

                
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[-1] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    wark = collections.deque()
    warp = collections.deque()

    wark.appendleft((Ch - 1, Cw - 1))
    visited[Ch - 1][Cw - 1] = 0
    while wark:
        h, w = wark.pop()
        warp.append((h, w))
        for mh, mw in move:
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                visited[ch][cw] = visited[h][w]
                wark.append((ch, cw))
        if len(wark) == 0:
            while warp:
                h, w = warp.pop()
                for wh in range(-2, 3):  # 移動B: ワープ魔法
                    for ww in range(-2, 3):
                        ch, cw = h + wh, w + ww
                        if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                            visited[ch][cw] = visited[h][w] + 1
                            wark.append((ch, cw))

    ret = visited[Dh - 1][Dw - 1]
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    ret = 10 ** 30
    q = [(0, sh-1, sw-1)]
    visited = set()
    while q:
        cnt, h, w = heappop(q)
        visited.add((h, w))
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0: continue
                if h+i < 0 or w+j < 0: continue
                if h+i >= H or w+j >= W: continue
                if field[h+i][w+j]  == "#": continue
                if (h+i, w+j) in visited: continue
                if max(i,j) == 1 and min(i,j) == 0:
                    heappush(q, (cnt, h+i, w+j))
                else:
                    heappush(q, (cnt+1, h+i, w+j))
    return -1

print(main())

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    if not((n==2 and m==(1 or 2 or 3))or(n==1 and m == 2)or(n == 3 and m ==2)):
                    	check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()