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

H,W = map(int,input().split(" "))
sy,sx = map(int,input().split(" "))
gy,gx = map(int,input().split(" "))
sx-=1
sy-=1
gx-=1
gy-=1

field = [ list(input()) for i in range(H) ]
dx = ( 1, 0,-1, 0 )
dy = ( 0, 1, 0,-1 )
wx = ( 2, 2, 2, 1, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1, 0, 1, 1, 2, 2 )
wy = ( 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1 )

# 徒歩探索候補キュー
q = deque()
q.append( (sx,sy) )
# ワープ探索候補キュー
q_warp = deque()

dist_ = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_warp = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_[sy][sx] = 0
dist_warp[sy][sx] = 0

while len(q_warp) > 0 or len(q) > 0:
    while len(q) > 0:
        # 親座標
        x,y = q.popleft()

        # 親座標から徒歩可能な全座標を探索
        for direction in range(4):
            # 徒歩探索する対象座標
            next_x = x + dx[direction]
            next_y = y + dy[direction]

            # 対象座標が領域外は無視
            if W <= next_x or H <= next_y or next_x < 0 or next_y < 0:
                continue
            # 対象座標が壁は無視
            if field[next_y][next_x] == '#':
                continue
            # 対象座標の徒歩探索済みなら無視
            if dist_[next_y][next_x] != -1:
                continue
            
            # 徒歩で行ける場所がワープ探索候補キューに入っている場合削除
            if (next_x,next_y) in q_warp:
                q_warp.remove( (next_x,next_y) )
            # 徒歩で行ける場所は同じワープ回数
            dist_warp[next_y][next_x] = dist_warp[y][x]

            dist_[next_y][next_x] = dist_[y][x] + 1
            q.append( ( next_x,next_y ) )

        # 親座標からワープ可能な全座標を探索
        for warp_direction in range(20):
            # ワープ探索する対象座標
            warp_x = x + wx[warp_direction]
            warp_y = y + wy[warp_direction]

            # 対象座標が領域外は無視
            if W <= warp_x or H <= warp_y or warp_x < 0 or warp_y < 0:
                continue
            # 対象座標が壁は無視
            if field[warp_y][warp_x] == '#':
                continue
            # 対象座標の徒歩探索済みなら無視
            if dist_[warp_y][warp_x] != -1:
                continue
            # 対象座標のワープ探索済みなら無視
            if dist_warp[warp_y][warp_x] != -1:
                continue
            
            dist_warp[warp_y][warp_x] = dist_warp[y][x] + 1
            q_warp.append( ( warp_x,warp_y ) )

    while len(q_warp) > 0: # 壁を超えた新しい領域になるまでキューを探す
        x,y = q_warp.popleft()
        if dist_[y][x] == -1: # この時点で徒歩未探索なのは、壁を超えている
            # 新しい領域に対して、新たな探索を行う準備
            dist_[y][x] = 0 
            q.append( (x,y) )
            break

print(dist_warp[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import pprint

H,W = map(int,input().split(" "))
sy,sx = map(int,input().split(" "))
gy,gx = map(int,input().split(" "))
sx-=1
sy-=1
gx-=1
gy-=1

field = [ list(input()) for i in range(H) ]
dx = ( 1, 0,-1, 0 )
dy = ( 0, 1, 0,-1 )
wx = ( 2, 2, 2, 1, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1, 0, 1, 1, 2, 2 )
wy = ( 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1 )

# 徒歩探索候補キュー
q = deque()
q.append( (sx,sy) )
# ワープ探索候補キュー
q_warp = deque()
# q_warp.append( (sx,sy) )

dist_ = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_warp = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_[sy][sx] = 0
dist_warp[sy][sx] = 0

while len(q_warp) > 0 or len(q) > 0:
    while len(q) > 0:
        # 親座標
        x,y = q.popleft()

        # 親座標から徒歩可能な全座標を探索
        for direction in range(4):
            # 徒歩探索する対象座標
            next_x = x + dx[direction]
            next_y = y + dy[direction]

            # 対象座標が領域外は無視
            if W <= next_x or H <= next_y or next_x < 0 or next_y < 0:
                continue
            # 対象座標が壁は無視
            if field[next_y][next_x] == '#':
                dist_[next_y][next_x] = '#'
                continue
            # 対象座標の徒歩探索済みなら無視
            if dist_[next_y][next_x] != -1:
                continue
            
            # 徒歩で行ける場所がワープ探索候補キューに入っている場合削除
            if (next_x,next_y) in q_warp:
                q_warp.remove( (next_x,next_y) )
            # 徒歩で行ける場所は同じワープ回数
            dist_warp[next_y][next_x] = dist_warp[y][x]

            dist_[next_y][next_x] = dist_[y][x] + 1
            q.append( ( next_x,next_y ) )

        # 親座標からワープ可能な全座標を探索
        for warp_direction in range(20):
            # ワープ探索する対象座標
            warp_x = x + wx[warp_direction]
            warp_y = y + wy[warp_direction]

            # 対象座標が領域外は無視
            if W <= warp_x or H <= warp_y or warp_x < 0 or warp_y < 0:
                continue
            # 対象座標が壁は無視
            if field[warp_y][warp_x] == '#':
                dist_[warp_y][warp_x] = '#'
                dist_warp[warp_y][warp_x] = '#'
                continue
            # 対象座標の徒歩探索済みなら無視
            if dist_[warp_y][warp_x] != -1:
                continue
            # 対象座標のワープ探索済みなら無視
            if dist_warp[warp_y][warp_x] != -1:
                continue
            
            dist_warp[warp_y][warp_x] = dist_warp[y][x] + 1
            q_warp.append( ( warp_x,warp_y ) )

    while len(q_warp) > 0: # 壁を超えた新しい領域になるまでキューを探す
        x,y = q_warp.popleft()
        if dist_[y][x] == -1: # この時点で徒歩未探索なのは、壁を超えている
            # 新しい領域に対して、新たな探索を行う準備
            dist_[y][x] = 0 
            q.append( (x,y) )
            break

print(dist_warp[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product


def main():
    h, w = map(int, input().split())
    c = tuple(map(lambda x: int(x)+1, input().split()))
    d = tuple(map(lambda x: int(x)+1, input().split()))
    s = ['#'*(w+4)] * 2
    for _ in range(h):
        s.append(f'##{input()}##')
    s.extend(['#'*(w+4)] * 2)

    move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
    move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

    cost = [[float('inf')] * (w+4) for _ in range(h+4)]
    cost[c[0]][c[1]] = 0
    yet = deque([(c[0], c[1], 0)])
    done = deque()

    while yet:
        y, x, m = yet.popleft()
        done.append((y, x, m))
        # Move A
        for dx, dy in move_a_area:
            hh, ww = y + dy, x + dx
            if s[hh][ww] == '#' or cost[hh][ww] <= m:
                continue
            cost[hh][ww] = m
            yet.append((hh, ww, m))
        # Move B
        if not yet:
            while done:
                y, x, m = done.popleft()
                for dx, dy in move_b_area:
                    hh, ww = y + dy, x + dx
                    if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                        continue
                    cost[hh][ww] = m + 1
                    yet.append((hh, ww, m + 1))

    print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = ['#'*(w+4)] * 2
for _ in range(h):
    s.append(f'##{input()}##')
s.extend(['#'*(w+4)] * 2)

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * (w+4) for _ in range(h+4)]
cost[c[0]][c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        yet.append((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                    continue
                cost[hh][ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        yet.append((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if not s[hh, ww] or cost[hh, ww] <= m + 1:
                    continue
                cost[hh, ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        yet.appendleft((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if not s[hh, ww] or cost[hh, ww] <= m + 1:
                    continue
                cost[hh, ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m + 1:
            continue
        cost[hh, ww] = m + 1
        que.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m + 1:
            continue
        cost[hh, ww] = m + 1
        que.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
 
import sys
from collections import deque 
INF = float('INF') #INFの宣言
#入力部
H, W = map(int, input().split())
Ch, Cw = map(lambda c: int(c) -1 , input().split())
Dh, Dw = map(lambda d: int(d) -1, input().split())
mymap = []
for h in range(H):
    mymap += [list(input())]
#各地点までの最短距離の配列,INFで初期化
d = [ [INF for w in range(W)] for h in range(H) ]
#obstacleの処理
for h in range(H):
    for w in range(W):
        if mymap[h][w] == '#':
            d[h][w] = -1
#移動4方向のベクトル
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  
 
def bfs(h, w):
    warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = warp_cnt     #スタート地点のwarp回数をresにする
    #warp先の座標を格納するリスト
    warp_deque = deque()
    # dequeが空になるまでループ
    while mydeque:
        while mydeque:
            #dequeの先頭を取り出す
            y, x = mydeque.popleft()
            warp_deque.append((y,x))
            for i in range(4):
                #移動後の点を(nx, ny) とする
                nx, ny = x + dx[i], y + dy[i]
                #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
                if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] >  d[y][x]:
                    #print(ny, nx, d[ny][nx], mymap[ny][nx])
                    if  mymap[ny][nx] != '#' : 
                    #移動できるならdequeに入れ、その点の距離をwarp_cntで確定する
                        mydeque.appendleft([ny, nx])
                        if d[ny][nx] > warp_cnt:
                            d[ny][nx] = warp_cnt
                            warp_deque.append((ny, nx))
        #Goalが探索済みであれば，探索をやめる
        if d[Dh][Dw] != INF:
            break
        #warpの処理
        warp_cnt += 1
        while warp_deque:
            h, w = warp_deque.popleft()
            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 d[i][j] > warp_cnt:
                        d[i][j] = warp_cnt
                        mydeque.append([i,j])
    return
 
 
bfs(Ch,Cw)

if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
 
import sys
from collections import deque 
INF = float('INF') #INFの宣言
#入力部
H, W = map(int, input().split())
Ch, Cw = map(lambda c: int(c) -1 , input().split())
Dh, Dw = map(lambda d: int(d) -1, input().split())
mymap = []
for h in range(H):
    mymap += [list(input())]
#各地点までの最短距離の配列,INFで初期化
d = [ [INF for w in range(W)] for h in range(H) ]
#移動4方向のベクトル
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  
 
def bfs(h, w):
    warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = warp_cnt     #スタート地点のwarp回数をresにする
    #warp先の座標を格納するリスト
    warp_deque = deque()
    # dequeが空になるまでループ
    while mydeque:
        while mydeque:
            #dequeの先頭を取り出す
            y, x = mydeque.popleft()
            warp_deque.append((y,x))
            for i in range(4):
                #移動後の点を(nx, ny) とする
                nx, ny = x + dx[i], y + dy[i]
                #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
                if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] >  d[y][x]:
                    #print(ny, nx, d[ny][nx], mymap[ny][nx])
                    if  mymap[ny][nx] != '#' : 
                    #移動できるならdequeに入れ、その点の距離をwarp_cntで確定する
                        mydeque.appendleft([ny, nx])
                        if d[ny][nx] > warp_cnt:
                            d[ny][nx] = warp_cnt
                            warp_deque.append((ny, nx))
                        #if ny == Dh and nx == Dw:
                        #            print(res)
                    elif mymap[ny][nx] == '#' :
                        #warpの可能性を探索する                
                            d[ny][nx] = -1
        #Goalが探索済みであれば，探索をやめる
        if d[Dh][Dw] != INF:
            break
        #warpの処理
        warp_cnt += 1
        while warp_deque:
            h, w = warp_deque.popleft()
            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 d[i][j] > warp_cnt and mymap[i][j] != '#':
                        d[i][j] = warp_cnt
                        mydeque.append([i,j])
        #warp_listを空にする
        #warp_list.clear()

    return
 
 
bfs(Ch,Cw)

if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
 
import sys
from collections import deque 
INF = float('INF') #INFの宣言
#入力部
H, W = map(int, input().split())
Ch, Cw = map(lambda c: int(c) -1 , input().split())
Dh, Dw = map(lambda d: int(d) -1, input().split())
mymap = []
for h in range(H):
    mymap += [list(input())]
#各地点までの最短距離の配列,INFで初期化
d = [ [INF for w in range(W)] for h in range(H) ]
#移動4方向のベクトル
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  
 
def bfs(h, w):
    warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = warp_cnt     #スタート地点のwarp回数をresにする
    #warp先の座標を格納するリスト
    warp_list = []
    # dequeが空になるまでループ
    while mydeque:
        while mydeque:
            #dequeの先頭を取り出す
            y, x = mydeque.popleft()
            warp_list.append((y,x))
            for i in range(4):
                #移動後の点を(nx, ny) とする
                nx, ny = x + dx[i], y + dy[i]
                #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
                if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] >  d[y][x]:
                    #print(ny, nx, d[ny][nx], mymap[ny][nx])
                    if  mymap[ny][nx] != '#' : 
                    #移動できるならdequeに入れ、その点の距離をwarp_cntで確定する
                        mydeque.appendleft([ny, nx])
                        if d[ny][nx] > warp_cnt:
                            d[ny][nx] = warp_cnt
                            warp_list.append((ny, nx))
                        #if ny == Dh and nx == Dw:
                        #            print(res)
                    elif mymap[ny][nx] == '#' :
                        #warpの可能性を探索する                
                            d[ny][nx] = -1
        #Goalが探索済みであれば，探索をやめる
        if d[Dh][Dw] != INF:
            break
        #warpの処理
        warp_cnt += 1
        for h,w in warp_list:
            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 d[i][j] > warp_cnt and mymap[i][j] != '#':
                        d[i][j] = warp_cnt
                        mydeque.append([i,j])
        #warp_listを空にする
        warp_list.clear()

    return
 
 
bfs(Ch,Cw)

if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

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

INF = 10**12
cost = [[INF] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m:
            cost[hh][ww] = m
            que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m + 1:
            cost[hh][ww] = m + 1
            que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[float("Inf") for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:

    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)

if reach[dx][dy] == float("Inf"):
    print(-1)
else:
    print(reach[dx][dy])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w = map(int, input().split())
    strt_y, strt_x = map(int, input().split())
    goal_y, goal_x = map(int, input().split())
    stage = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                stage[i+2][j+2] = float("inf")
    strt_y += 1
    strt_x += 1
    goal_y += 1
    goal_x += 1
    hq = [[0, strt_y, strt_x]]
    stage[strt_y][strt_x] = 0
    while len(hq) > 0:
        pt, crr_y, crr_x = heapq.heappop(hq)
        if stage[crr_y][crr_x] < pt:
            continue
        for i in range(crr_y-2, crr_y+2+1):
            for j in range(crr_x-2, crr_x+2+1):
                if abs(crr_y-i) + abs(crr_x-j) == 1:
                    if pt < stage[i][j]:
                        stage[i][j] = pt
                        heapq.heappush(hq, [pt, i, j])
                else:
                    if pt+1 < stage[i][j]:
                        stage[i][j] = pt+1
                        heapq.heappush(hq, [pt+1, i, j])
    if stage[goal_y][goal_x] == float("inf"):
        print(-1)
    else:
        print(stage[goal_y][goal_x])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.deque()
q.append([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

cnt = 0
while len(q) != 0:
    cnt += 1
    crntY, crntX = q.popleft()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
            q.append([nextY, nextX])
        else:
            q.appendleft([nextY, nextX])
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Submission status: Time Limit Exceeded

Solution code:
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.Queue()
q.put([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

while q.qsize() != 0:
    crntY, crntX = q.get()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        q.put([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]

check = [[float('inf') for i in range(W)] for j in range(H)]
walk = [(0,-1), (0,1), (-1,0), (1,0)]
qu = deque([(Si-1, Sj-1)])
check[Si-1][Sj-1] = 0

while qu:
    i, j = qu.popleft()
    cost = check[i][j]
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj))
    #ワープで行けるところ
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i+di < H and 0 <= j+dj < W:
                if not maze[i+di][0][j+dj] == '#':
                    if check[i+di][j+dj] > cost + 1:
                        check[i+di][j+dj] = cost + 1
                        qu.append((i+di, j+dj))

#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])