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:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

H, W = MI()
Ch, Cw = MI()
Dh, Dw = MI()
S_ = []
for i in range(H):
    s = S()
    S_.append(s)

# i行目j列目のマスに(i - 1) * W + j　- 1の数字を割り振る
star = (Ch - 1) * W + Cw - 1
goal = (Dh - 1) * W + Dw - 1
g = [[] for _ in range(H * W)]
for i in range(H * W):
    h, w = divmod(i, W)
    if S_[h][w] == '#':
        continue
    else:
        if w != 0 and S_[h][w - 1] == '.':
            g[i].append(i - 1)
        if w != W - 1 and S_[h][w + 1] == '.':
            g[i].append(i + 1)
        if h != 0 and S_[h - 1][w] == '.':
            g[i].append(i - W)
        if h != (H - 1) and S_[h + 1][w] == '.':
            g[i].append(i + W)


from collections import deque

def bfs(u, n):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    dif_list = [u]
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = 0
                queue.append(i)
                dif_list.append(i)
    return dif_list

def warp(A, B):
    dif_A = []
    bfs_list = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)
        a_list = []
        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                a_list.append(a_)

        for a_ in a_list:
            h_, w_ = divmod(a_, W)
            if 0 <= a_ <= H * W - 1 and a_ not in B and a_ not in dif_A and S_[h_][w_] == '.':
                dif_A.append(a_)
    for b in dif_A:
        if b not in bfs_list:
            for c in bfs(b, H * W):
                if c not in dif_A:
                    bfs_list.append(c)
                    dif_A.append(c)
    return dif_A

dif_0 = bfs(star, H * W)
dif_total = dif_0
ans = 0
if goal in dif_0:
    print(0)
    exit()
else:
    while dif_0 != []:
        dif_0 = warp(dif_0, dif_total)
        dif_total += dif_0
        ans += 1
        if goal in dif_0:
            print(ans)
            exit()
    print(-1)

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)]
    while q:
        cnt, h, w = heappop(q)
        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 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:
inf = 10 ** 9
from collections import deque
def bfs(sx, sy):
    cost = [[inf] * w for i in range(h)]
    d = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
    cost[sx - 1][sy - 1] = 0
    q = deque()
    q.append((sx - 1, sy - 1))
    
    while q:
        s, t = q.popleft()
        for dx, dy in d:
            nx = s + dx
            ny = t + dy
            
            if not(0 <= nx < h and 0 <= ny < w):continue
            if cost[nx][ny] <= cost[s][t]:continue
            if (dx + dy)%2 == 0:
                if c[nx][ny] == '.' and cost[nx][ny] > cost[s][t] + 1:
                    cost[nx][ny] = cost[s][t] + 1
                    if (nx, ny) != (dh - 1, dw - 1):
                        q.append((nx, ny))

                next_d = ((dx, 0), (0, dy), (dx, dy))
                for ddx, ddy in next_d:
                    nnx = nx + ddx
                    nny = ny + ddy
                    if not(0 <= nnx < h and 0 <= nny < w):continue
                    if c[nnx][nny] == '#':continue
                    if cost[nnx][nny] <= cost[s][t] + 1:continue
                    cost[nnx][nny] = cost[s][t] + 1
                    
                    if (nnx, nny) == (dh - 1, dw - 1):continue
                    q.append((nnx, nny))
                continue
                    
            elif c[nx][ny] == '.':
                cost[nx][ny] = min(cost[nx][ny], cost[s][t])
                
            elif c[nx][ny] == '#':
                nx += dx
                ny += dy
                if not(0 <= nx < h and 0 <= ny < w):continue
                if c[nx][ny] == '#':continue
                if cost[nx][ny] <= cost[s][t] + 1:continue
                cost[nx][ny] = cost[s][t] + 1
                
            if (nx, ny) == (dh - 1, dw - 1):continue
            q.append((nx, ny))

    return cost[dh - 1][dw - 1]
        
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
c = [list(input()) for _ in range(h)]

res = bfs(ch, cw)
print(res if res != inf else -1)

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)

    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] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    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))
        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

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

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 = [-1] * W
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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] == -1:
                status[sH][sW] = tmpIndex
                q.insert(0, (sH, sW, tmpIndex))
            else:
                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] == -1:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex, tmpIndex))
                else:
                    if status[_hIndex][_wIndex] > tmpIndex:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))

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


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

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

H, W = MI()
Ch, Cw = MI()
Dh, Dw = MI()
S_ = []
for i in range(H):
    s = S()
    S_.append(s)

# i行目j列目のマスに(i - 1) * W + j　- 1の数字を割り振る
star = (Ch - 1) * W + Cw - 1
goal = (Dh - 1) * W + Dw - 1
g = [[] for _ in range(H * W)]
for i in range(H * W):
    h, w = divmod(i, W)
    if S_[h][w] == '#':
        continue
    else:
        if w != 0 and S_[h][w - 1] == '.':
            g[i].append(i - 1)
        if w != W - 1 and S_[h][w + 1] == '.':
            g[i].append(i + 1)
        if h != 0 and S_[h - 1][w] == '.':
            g[i].append(i - W)
        if h != (H - 1) and S_[h + 1][w] == '.':
            g[i].append(i + W)


from collections import deque

def bfs(u, n):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    dif_list = [u]
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = 0
                queue.append(i)
                dif_list.append(i)
    return dif_list

def warp(A, B):
    dif_A = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)
        a_list = []
        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                a_list.append(a_)

        for a_ in a_list:
            h_, w_ = divmod(a_, W)
            if 0 <= a_ <= H * W - 1 and a_ not in B and a_ not in dif_A and S_[h_][w_] == '.':
                dif_A.append(a_)
    bfs_list = []
    for b in dif_A:
        if b not in bfs_list:
            for c in bfs(b, H * W):
                if c not in dif_A:
                    bfs_list.append(c)
                    dif_A.append(c)
    return dif_A

dif_0 = bfs(star, H * W)
dif_total = dif_0
ans = 0
if goal in dif_0:
    print(0)
    exit()
else:
    while dif_0 != []:
        dif_0 = warp(dif_0, dif_total)
        dif_total += dif_0
        ans += 1
        if goal in dif_0:
            print(ans)
            exit()
    print(-1)

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

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 = [-1] * W
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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] == '.':
                tmpIndex = index
                if status[sH][sW] == -1:
                    status[sH][sW] = tmpIndex
                    q.insert(0, (sH, sW, tmpIndex))
                else:
                    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] == '.':
                    tmpIndex = index + 1
                    if status[_hIndex][_wIndex] == -1:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))
                    else:
                        if status[_hIndex][_wIndex] > tmpIndex:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))

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


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

Submission status: Time Limit Exceeded

Solution code:
inf = 10 ** 9
from collections import deque
def bfs(sx, sy):
    cost = [[inf] * w for i in range(h)]
    d = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
    cost[sx - 1][sy - 1] = 0
    q = deque()
    q.append((sx - 1, sy - 1))
    
    while q:
        s, t = q.popleft()
        for dx, dy in d:
            nx = s + dx
            ny = t + dy
            
            if not(0 <= nx < h and 0 <= ny < w):continue
            if cost[nx][ny] <= cost[s][t]:continue
            if (dx + dy)%2 == 0:
                if c[nx][ny] == '.' and cost[nx][ny] > cost[s][t] + 1:
                    cost[nx][ny] = cost[s][t] + 1
                    if (nx, ny) != (dh - 1, dw - 1):
                        q.append((nx, ny))

                next_d = ((dx, 0), (0, dy), (dx, dy))
                for ddx, ddy in next_d:
                    nnx = nx + ddx
                    nny = ny + ddy
                    if not(0 <= nnx < h and 0 <= nny < w):continue
                    if c[nnx][nny] == '#':continue
                    if cost[nnx][nny] <= cost[s][t] + 1:continue
                    cost[nnx][nny] = cost[s][t] + 1
                    
                    if (nnx, nny) == (dh - 1, dw - 1):continue
                    q.append((nnx, nny))
                continue
                    
            elif c[nx][ny] == '.' and (dx + dy)%2 != 0:
                cost[nx][ny] = min(cost[nx][ny], cost[s][t])
                
            elif c[nx][ny] == '#' and (dx + dy)%2 != 0:
                nx += dx
                ny += dy
                if not(0 <= nx < h and 0 <= ny < w):continue
                if c[nx][ny] == '#':continue
                if cost[nx][ny] <= cost[s][t] + 1:continue
                cost[nx][ny] = cost[s][t] + 1
                
            if (nx, ny) == (dh - 1, dw - 1):continue
            q.append((nx, ny))

    return cost
        
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
c = [list(input()) for _ in range(h)]

res = bfs(ch, cw)
if res[dh - 1][dw - 1] == inf:print(-1)
else:print(res[dh - 1][dw - 1])

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

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 = [-1] * W
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.insert(0, (sH, sW, tmpIndex))
                    else:
                        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] == '.':
                    tmpIndex = index + 1
                    if status[_hIndex][_wIndex] == -1:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))
                    else:
                        if status[_hIndex][_wIndex] > tmpIndex:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))

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


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)

    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] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    if maze[ny][nx] == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif maze[ny][nx] == '#':
                        pass
                    elif maze[ny][nx] > curg + 1:
                        maze[ny][nx] = curg + 1
                        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

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

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 = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.append((sH, sW, tmpIndex))
                    else:
                        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] == '.':
                    tmpIndex = index + 1
                    if status[_hIndex][_wIndex] == -1:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))
                    else:
                        if status[_hIndex][_wIndex] > tmpIndex:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))

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


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

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

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 = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.insert(0, (sH, sW, tmpIndex))
                    else:
                        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] == '.':
                    tmpIndex = index + 1
                    if status[_hIndex][_wIndex] == -1:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))
                    else:
                        if status[_hIndex][_wIndex] > tmpIndex:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
sy,sx=[int(i)-1 for i in input().split()]
gy,gx=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='#':
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)

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

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

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 = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

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

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

        if (status[hIndex][wIndex] > 0) and (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) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.insert(0, (sH, sW, tmpIndex))
                    else:
                        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 (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex, _wIndex) in sss:
                    continue

                if arr[_hIndex][_wIndex] == '.':
                    tmpIndex = index + 1
                    if status[_hIndex][_wIndex] == -1:
                        status[_hIndex][_wIndex] = tmpIndex
                        q.append((_hIndex, _wIndex, tmpIndex))
                    else:
                        if status[_hIndex][_wIndex] > tmpIndex:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))

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


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