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 sys
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 = tuple(['#'] * (w + 4))
    maze = {e:[] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0
    #maze2 = [[1] * (w + 4) for _ in range(h + 4)]
    #maze3 = [[1] * (w + 4) for _ in range(h + 4)]

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    while next_nodes:
        for nextn in  next_nodes:
            (nextny, nextnx) = nextn
            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.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((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:
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 = tuple(['#'] * (w + 4))
    maze = {e:[] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    while next_nodes:
        for nextn in  next_nodes:
            (nextny, nextnx) = nextn
            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.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((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:
# https://atcoder.jp/contests/abc176/submissions/16164430?lang=ja
import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  _, (curr_h, curr_w) = heapq.heappop(Q)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.append([childy, childx])

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

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 = []
    dif_A_total = [0] * (H * W)
    bfs_list = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)

        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                h_, w_ = divmod(a_, W)
                if 0 <= a_ <= H * W - 1 and B[a_] == 0 and dif_A_total[a_] == 0 and S_[h_][w_] == '.':
                    dif_A_total[a_] = 1
                    B[a_] = 1
                    dif_A.append(a_)
    for b in dif_A:
        if b not in bfs_list:
            b_ = bfs(b, H * W)
            for c in b_:
                if c not in dif_A:
                    bfs_list.append(c)
                    dif_A.append(c)
                    B[c] = 1
    return dif_A

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
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 = tuple(['#'] * (w + 4))
    maze = {e:[] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    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.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((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 = deque(set(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:
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

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    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.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((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 = deque(set(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())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
while d:
    py, px = d.popleft()
    #bfs
    if py-1 >= 0 and s[py-1][px] == "." and meiro[py-1][px] > meiro[py][px]:
        d.append([py-1, px])
        meiro[py-1][px] = meiro[py][px]

    if py+1 < h and s[py+1][px] == "." and meiro[py+1][px]>meiro[py][px]:
        d.append([py+1, px])
        meiro[py+1][px] = meiro[py][px]

    if px+1 < w and s[py][px+1] == "." and meiro[py][px+1]>meiro[py][px]:
        d.append([py, px+1])
        meiro[py][px+1] = meiro[py][px]

    if px-1 >= 0 and s[py][px-1] == "." and meiro[py][px-1]>meiro[py][px]:
        d.append([py, px-1])
        meiro[py][px-1] = meiro[py][px]

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

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([])
nxt_st_all = set([])

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    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 and not (hs, ws) in nxt:
                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
def main():
    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])


main()

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([])
nxt_st_all = set([])

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    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
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
while d:
    py, px = d.popleft()
    #bfs
    if py-1 >= 0 and s[py-1][px] == "." and meiro[py-1][px] > meiro[py][px]:
        child_up = [py-1, px]
        d.append(child_up)
        meiro[py-1][px] = meiro[py][px]

    if py+1 < h and s[py+1][px] == "." and meiro[py+1][px]>meiro[py][px]:
        child_down = [py+1, px]
        d.append(child_down)
        meiro[py+1][px] = meiro[py][px]

    if px+1 < w and s[py][px+1] == "." and meiro[py][px+1]>meiro[py][px]:
        child_right = [py, px+1]
        d.append(child_right)
        meiro[py][px+1] = meiro[py][px]

    if px-1 >= 0 and s[py][px-1] == "." and meiro[py][px-1]>meiro[py][px]:
        child_left = [py, px-1]
        d.append(child_left)
        meiro[py][px-1] = meiro[py][px]

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

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 = []
    dif_A_total = [0] * (H * W)
    bfs_list = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)

        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                h_, w_ = divmod(a_, W)
                if 0 <= a_ <= H * W - 1 and B[a_] == 0 and dif_A_total[a_] == 0 and S_[h_][w_] == '.':
                    dif_A_total[a_] = 1
                    B[a_] = 1
                    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)
                    B[c] = 1
    return dif_A

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

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([])
nxt_st_all = 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 and not (hs, ws) in nxt_st_all:
                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 and not (hs, ws) in nxt_st_all | nxt:
                nxt.add((hs, ws))

    return nxt

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

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([])
nxt_st_all = 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 and not (hs, ws) in nxt_st_all:
                nxt.add((hs, ws))

    return nxt

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

from sys import stdin
readline = stdin.readline

from builtins import max, min, range

INF = 10 ** 6

H, W = map(int, readline().split())
C1, C2 = map(lambda x: int(x) - 1, readline().split())
D1, D2 = map(lambda x: int(x) - 1, readline().split())
S = [readline()[:-1] 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:
#!/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 and not (hs, ws) in pnxt:
                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)