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
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

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

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.append((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos

        for dh, dw in product(range(-2,3), repeat=2):
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.appendleft((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.append((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**6
walk_area=[(1,0), (0,1), (-1,0), (0,-1)]
warp_area=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        warp_area.append((i, j))

def main():
    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) + 1, input().split())
    dh, dw = map(lambda x: int(x) + 1, input().split())
    S = ['#'*(w+4)]
    S.append('#'*(w+4))
    for i in range(h):
        S.append('##'+input()+'##')
    S.append('#'*(w+4))
    S.append('#'*(w+4))
    
    # 各場所までワープ何回で辿り着くか
    COST = [[INF for i in range(w+4)] for j in range(h+4)]
    COST[ch][cw] = 0

    d = deque([[ch,cw,0]])
    d2 = deque()
    while len(d) > 0:
        t = d.popleft()
        d2.append(t)
        x = t[0]
        y = t[1]
        num = t[2] # COST[x][y]
        for dx, dy in walk_area:
            X = x + dx
            Y = y + dy
            if S[X][Y] == '#' or COST[X][Y] <= num:
                continue
        
            COST[X][Y] = num
            d.append([X, Y, num])
        if not d:
            while len(d2) > 0:
                x, y, num = d2.popleft()
                for dx, dy in warp_area:
                    X = x + dx
                    Y = y + dy
                    if S[X][Y] == '#' or COST[X][Y] <= num+1:
                        continue
                    
                    COST[X][Y] = num + 1
                    d.append([X, Y, num + 1])
    # for i in COST:
    #     print(i)
    if COST[dh][dw] == 10**6:
        print(-1)
    else:
        print(COST[dh][dw])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
#def input():
#  return sys.stdin.readline()[:-1]

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
S=['X'*(W+4), 'X'*(W+4)]+['XX'+input()+'XX' for _ in range(H)]+['X'*(W+4), 'X'*(W+4)]
T=[[10**6]*(W+4) for _ in range(H+4)]

import heapq
q=[[0, Ch, Cw]]
heapq.heapify(q)
T[Ch][Cw]=0

while q:
  c, a, b=heapq.heappop(q)
  if T[a-2][b-2]>c+1 and S[a-2][b-2]=='.':
    heapq.heappush(q, [c+1, a-2, b-2])
    T[a-2][b-2]=c+1
  if T[a-2][b-1]>c+1 and S[a-2][b-1]=='.':
    heapq.heappush(q, [c+1, a-2, b-1])
    T[a-2][b-1]=c+1
  if T[a-2][b]>c+1 and S[a-2][b]=='.':
    heapq.heappush(q, [c+1, a-2, b])
    T[a-2][b]=c+1
  if T[a-2][b+1]>c+1 and S[a-2][b+1]=='.':
    heapq.heappush(q, [c+1, a-2, b+1])
    T[a-2][b+1]=c+1
  if T[a-2][b+2]>c+1 and S[a-2][b+2]=='.':
    heapq.heappush(q, [c+1, a-2, b+2])
    T[a-2][b+2]=c+1
    
  if T[a-1][b-2]>c+1 and S[a-1][b-2]=='.':
    heapq.heappush(q, [c+1, a-1, b-2])
    T[a-1][b-2]=c+1
  if T[a-1][b-1]>c+1 and S[a-1][b-1]=='.':
    heapq.heappush(q, [c+1, a-1, b-1])
    T[a-1][b-1]=c+1
  if T[a-1][b]>c and S[a-1][b]=='.':
    heapq.heappush(q, [c, a-1, b])
    T[a-1][b]=c
  if T[a-1][b+1]>c+1 and S[a-1][b+1]=='.':
    heapq.heappush(q, [c+1, a-1, b+1])
    T[a-1][b+1]=c+1
  if T[a-1][b+2]>c+1 and S[a-1][b+2]=='.':
    heapq.heappush(q, [c+1, a-1, b+2])
    T[a-1][b+2]=c+1
  
  if T[a][b-2]>c+1 and S[a][b-2]=='.':
    heapq.heappush(q, [c+1, a, b-2])
    T[a][b-2]=c+1
  if T[a][b-1]>c and S[a][b-1]=='.':
    heapq.heappush(q, [c, a, b-1])
    T[a][b-1]=c
  if T[a][b+1]>c and S[a][b+1]=='.':
    heapq.heappush(q, [c, a, b+1])
    T[a][b+1]=c
  if T[a][b+2]>c+1 and S[a][b+2]=='.':
    heapq.heappush(q, [c+1, a, b+2])
    T[a][b+2]=c+1
  
  if T[a+1][b-2]>c+1 and S[a+1][b-2]=='.':
    heapq.heappush(q, [c+1, a+1, b-2])
    T[a+1][b-2]=c+1
  if T[a+1][b-1]>c+1 and S[a+1][b-1]=='.':
    heapq.heappush(q, [c+1, a+1, b-1])
    T[a+1][b-1]=c+1
  if T[a+1][b]>c and S[a+1][b]=='.':
    heapq.heappush(q, [c, a+1, b])
    T[a+1][b]=c
  if T[a+1][b+1]>c+1 and S[a+1][b+1]=='.':
    heapq.heappush(q, [c+1, a+1, b+1])
    T[a+1][b+1]=c+1
  if T[a+1][b+2]>c+1 and S[a+1][b+2]=='.':
    heapq.heappush(q, [c+1, a+1, b+2])
    T[a+1][b+2]=c+1
  
  if T[a+2][b-2]>c+1 and S[a+2][b-2]=='.':
    heapq.heappush(q, [c+1, a+2, b-2])
    T[a+2][b-2]=c+1
  if T[a+2][b-1]>c+1 and S[a+2][b-1]=='.':
    heapq.heappush(q, [c+1, a+2, b-1])
    T[a+2][b-1]=c+1
  if T[a+2][b]>c+1 and S[a+2][b]=='.':
    heapq.heappush(q, [c+1, a+2, b])
    T[a+2][b]=c+1
  if T[a+2][b+1]>c+1 and S[a+2][b+1]=='.':
    heapq.heappush(q, [c+1, a+2, b+1])
    T[a+2][b+1]=c+1
  if T[a+2][b+2]>c+1 and S[a+2][b+2]=='.':
    heapq.heappush(q, [c+1, a+2, b+2])
    T[a+2][b+2]=c+1
    
if T[Dh][Dw]<10**6:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()[:-1]

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
S=['X'*(W+4), 'X'*(W+4)]+['XX'+input()+'XX' for _ in range(H)]+['X'*(W+4), 'X'*(W+4)]
T=[[10**6]*(W+4) for _ in range(H+4)]

import heapq
q=[[0, Ch, Cw]]
heapq.heapify(q)
T[Ch][Cw]=0

while q:
  c, a, b=heapq.heappop(q)
  if T[a-2][b-2]>c+1 and S[a-2][b-2]=='.':
    heapq.heappush(q, [c+1, a-2, b-2])
    T[a-2][b-2]=c+1
  if T[a-2][b-1]>c+1 and S[a-2][b-1]=='.':
    heapq.heappush(q, [c+1, a-2, b-1])
    T[a-2][b-1]=c+1
  if T[a-2][b]>c+1 and S[a-2][b]=='.':
    heapq.heappush(q, [c+1, a-2, b])
    T[a-2][b]=c+1
  if T[a-2][b+1]>c+1 and S[a-2][b+1]=='.':
    heapq.heappush(q, [c+1, a-2, b+1])
    T[a-2][b+1]=c+1
  if T[a-2][b+2]>c+1 and S[a-2][b+2]=='.':
    heapq.heappush(q, [c+1, a-2, b+2])
    T[a-2][b+2]=c+1
    
  if T[a-1][b-2]>c+1 and S[a-1][b-2]=='.':
    heapq.heappush(q, [c+1, a-1, b-2])
    T[a-1][b-2]=c+1
  if T[a-1][b-1]>c+1 and S[a-1][b-1]=='.':
    heapq.heappush(q, [c+1, a-1, b-1])
    T[a-1][b-1]=c+1
  if T[a-1][b]>c and S[a-1][b]=='.':
    heapq.heappush(q, [c, a-1, b])
    T[a-1][b]=c
  if T[a-1][b+1]>c+1 and S[a-1][b+1]=='.':
    heapq.heappush(q, [c+1, a-1, b+1])
    T[a-1][b+1]=c+1
  if T[a-1][b+2]>c+1 and S[a-1][b+2]=='.':
    heapq.heappush(q, [c+1, a-1, b+2])
    T[a-1][b+2]=c+1
  
  if T[a][b-2]>c+1 and S[a][b-2]=='.':
    heapq.heappush(q, [c+1, a, b-2])
    T[a][b-2]=c+1
  if T[a][b-1]>c and S[a][b-1]=='.':
    heapq.heappush(q, [c, a, b-1])
    T[a][b-1]=c
  if T[a][b+1]>c and S[a][b+1]=='.':
    heapq.heappush(q, [c, a, b+1])
    T[a][b+1]=c
  if T[a][b+2]>c+1 and S[a][b+2]=='.':
    heapq.heappush(q, [c+1, a, b+2])
    T[a][b+2]=c+1
  
  if T[a+1][b-2]>c+1 and S[a+1][b-2]=='.':
    heapq.heappush(q, [c+1, a+1, b-2])
    T[a+1][b-2]=c+1
  if T[a+1][b-1]>c+1 and S[a+1][b-1]=='.':
    heapq.heappush(q, [c+1, a+1, b-1])
    T[a+1][b-1]=c+1
  if T[a+1][b]>c and S[a+1][b]=='.':
    heapq.heappush(q, [c, a+1, b])
    T[a+1][b]=c
  if T[a+1][b+1]>c+1 and S[a+1][b+1]=='.':
    heapq.heappush(q, [c+1, a+1, b+1])
    T[a+1][b+1]=c+1
  if T[a+1][b+2]>c+1 and S[a+1][b+2]=='.':
    heapq.heappush(q, [c+1, a+1, b+2])
    T[a+1][b+2]=c+1
  
  if T[a+2][b-2]>c+1 and S[a+2][b-2]=='.':
    heapq.heappush(q, [c+1, a+2, b-2])
    T[a+2][b-2]=c+1
  if T[a+2][b-1]>c+1 and S[a+2][b-1]=='.':
    heapq.heappush(q, [c+1, a+2, b-1])
    T[a+2][b-1]=c+1
  if T[a+2][b]>c+1 and S[a+2][b]=='.':
    heapq.heappush(q, [c+1, a+2, b])
    T[a+2][b]=c+1
  if T[a+2][b+1]>c+1 and S[a+2][b+1]=='.':
    heapq.heappush(q, [c+1, a+2, b+1])
    T[a+2][b+1]=c+1
  if T[a+2][b+2]>c+1 and S[a+2][b+2]=='.':
    heapq.heappush(q, [c+1, a+2, b+2])
    T[a+2][b+2]=c+1
    
if T[Dh][Dw]<10**6:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

INF = 10**6
walk_area=[(1,0), (0,1), (-1,0), (0,-1)]
warp_area=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        warp_area.append((i, j))

def plus1(string):
    return int(string) + 1

def main():
    h, w = map(int, input().split())
    ch, cw = map(plus1, input().split())
    dh, dw = map(plus1, input().split())
    S = ['#'*(w+4)]
    S.append('#'*(w+4))
    for i in range(h):
        S.append('##'+input()+'##')
    S.append('#'*(w+4))
    S.append('#'*(w+4))
    
    # 各場所までワープ何回で辿り着くか
    COST = [[INF for i in range(w+4)] for j in range(h+4)]
    COST[ch][cw] = 0

    d = deque([[ch,cw,0]])
    d2 = deque()
    while len(d) > 0:
        t = d.popleft()
        d2.append(t)
        x = t[0]
        y = t[1]
        num = t[2] # COST[x][y]
        for dx, dy in walk_area:
            X = x + dx
            Y = y + dy
            if S[X][Y] == '#' or COST[X][Y] <= num:
                continue
            else:
                COST[X][Y] = num
                d.append([X, Y, num])
        if not d:
            while len(d2) > 0:
                t = d2.popleft()
                x = t[0]
                y = t[1]
                num = t[2] # COST[x][y]
                for dx, dy in warp_area:
                    X = x + dx
                    Y = y + dy
                    if S[X][Y] == '#' or COST[X][Y] <= num+1:
                        continue
                    else:
                        COST[X][Y] = num + 1
                        d.append([X, Y, num + 1])
    # for i in COST:
    #     print(i)
    if COST[dh][dw] == 10**6:
        print(-1)
    else:
        print(COST[dh][dw])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

INF = 10**6
walk_area=[(1,0), (0,1), (-1,0), (0,-1)]
warp_area=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        warp_area.append((i, j))

def plus1(string):
    return int(string) + 1

def main():
    h, w = map(int, input().split())
    ch, cw = map(plus1, input().split())
    dh, dw = map(plus1, input().split())
    S = ['#'*(w+4)]
    S.append('#'*(w+4))
    for i in range(h):
        S.append('##'+input()+'##')
    S.append('#'*(w+4))
    S.append('#'*(w+4))
    
    # 各場所までワープ何回で辿り着くか
    COST = [[INF for i in range(w+4)] for j in range(h+4)]
    COST[ch][cw] = 0

    d = deque([[ch,cw]])
    d2 = deque()
    while len(d) > 0:
        t = d.popleft()
        d2.append(t)
        x = t[0]
        y = t[1]
        num = COST[x][y]
        for dx, dy in walk_area:
            X = x + dx
            Y = y + dy
            if S[X][Y] == '#' or COST[X][Y] <= num:
                continue
            else:
                COST[X][Y] = num
                d.append([X, Y])
        if not d:
            while len(d2) > 0:
                t = d2.popleft()
                x = t[0]
                y = t[1]
                num = COST[x][y]
                for dx, dy in warp_area:
                    X = x + dx
                    Y = y + dy
                    if S[X][Y] == '#' or COST[X][Y] <= num+1:
                        continue
                    else:
                        COST[X][Y] = num + 1
                        d.append([X, Y])
    # for i in COST:
    #     print(i)
    if COST[dh][dw] == 10**6:
        print(-1)
    else:
        print(COST[dh][dw])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
visited = []
visited.append([ch-1, cw-1])

def check_pos(s, x, y, dx, dy, visited):
    if x+dx < 0 or x+dx >= w:
        return
    if y+dy < 0 or y+dy >= h:
        return

    if s[y+dy][x+dx] == ".":
        if [y+dy, x+dx] not in visited:
            visited.append([y+dy, x+dx])
            check_around(s, x+dx, y+dy, visited)


def check_around(s, x, y, visited):
    check_pos(s, x, y, 1, 0, visited)
    check_pos(s, x, y, 0, 1, visited)
    check_pos(s, x, y, 0, -1, visited)
    check_pos(s, x, y, -1, 0, visited)

def warp(x, y, visited, s):
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if dx == 0 and dy == 0:
                continue
            if x+dx < 0 or x+dx >= w:
                continue
            if y+dy < 0 or y+dy >= h:
                continue

            if s[y+dy][x+dx] == ".":
                if [y+dy, x+dx] not in visited:
                    visited.append([y+dy, x+dx])


def second_move(visited, s):
    prev_visted = copy.deepcopy(visited)
    for visited_pos in prev_visited:
        warp(visited_pos[1], visited_pos[0], visited, s)

count = 0
is_finish = False

while not is_finish and visited:
    prev_visited = copy.deepcopy(visited)
    for visited_pos in prev_visited:
        check_around(s, visited_pos[0], visited_pos[1], visited)

    for visited_pos in visited:
        if visited_pos[0]+1 == dh and visited_pos[1]+1 == dw:
            print(count)
            is_finish = True
            break
    second_move(visited, s)
    count += 1
    if visited == prev_visited and not is_finish:
        print("-1")
        is_finish = True

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
si,sj=map(int,input().split())
di,dj=map(int,input().split())

D =[f'{input()}' for _ in range(H)]


# デキューを用意する
from collections import deque
d = deque()

si-=1
sj-=1
di-=1
dj-=1
fx = [1,0,-1,0]
fy = [0,1,0,-1]

ans = [[float('inf')] * (W) for _ in range(H)]
p = 0
Done = []
d.append((si,sj,p))


while len(d) !=0:
    i,j,pp = d.popleft()
    if (i,j) in Done:continue
    Done.append((i,j))
    ans[i][j] = pp
    
    for x,y in zip(fx,fy):

        if i+x < 0 or i+x > H-1 or j+y <0 or j+y >W-1: continue
        if D[i+x][j+y] == "#":continue
        if ans[i+x][j+y] <= ans[i][j] :continue
        if (i+x,j+y) in Done :continue
        d.appendleft((i+x,j+y,ans[i][j] ))

    for mx in range(-2,3):
        for my in range(-2,3):
            if i+mx < 0 or i+mx > H-1 or j+my <0 or j+my >W-1: continue
            if D[i+mx][j+my] == "#":continue
            if ans[i+mx][j+my] <= ans[i][j] + 1 :continue
            if (i+mx,j+my) in Done :continue
            d.append((i+mx,j+my,ans[i][j]+1))
            
if ans[di][dj] == float('inf') :
  print(-1)
else:
  print(ans[di][dj])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue0 = deque([[ch-1, cw-1, 0]])
queue1 = deque()
while queue0:  
  x,y,c=queue0.popleft()
  queue1.append((x,y,c))
  for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=c:
      continue
    temp[xtemp][ytemp]=c
    queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
    
  if len(queue0)==0:      
    while queue1:
      x,y,c=queue1.popleft()
      for i,j in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        xtemp,ytemp=x+i,y+j
        if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
          continue
        if temp[xtemp][ytemp]<=c+1:
          continue
        temp[xtemp][ytemp]=c+1
        queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
        
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
si,sj=map(int,input().split())
di,dj=map(int,input().split())

D =[]
for i in range(H):
  D.append([])
  tmp = input()
  for j in range(W):
  	D[i].append(tmp[j])


# デキューを用意する
from collections import deque
d = deque()

si-=1
sj-=1
di-=1
dj-=1
fx = [1,0,-1,0]
fy = [0,1,0,-1]

ans = [[float('inf')] * (W) for _ in range(H)]
p = 0
Done = []
d.append((si,sj,p))


while len(d) !=0:
    i,j,pp = d.popleft()
    if (i,j) in Done:continue
    Done.append((i,j))
    ans[i][j] = pp
    
    for x,y in zip(fx,fy):

        if i+x < 0 or i+x > H-1 or j+y <0 or j+y >W-1: continue
        if D[i+x][j+y] == "#":continue
        if ans[i+x][j+y] <= ans[i][j] :continue
        if (i+x,j+y) in Done :continue
        d.appendleft((i+x,j+y,ans[i][j] ))

    for mx in range(-2,3):
        for my in range(-2,3):
            if i+mx < 0 or i+mx > H-1 or j+my <0 or j+my >W-1: continue
            if D[i+mx][j+my] == "#":continue
            if ans[i+mx][j+my] <= ans[i][j] + 1 :continue
            if (i+mx,j+my) in Done :continue
            d.append((i+mx,j+my,ans[i][j]+1))
            
if ans[di][dj] == float('inf') :
  print(-1)
else:
  print(ans[di][dj])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if 0<=ny<h and 0<=nx<w and maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if 0<=ny<h and 0<=nx<w and cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

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

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

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

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]


def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_


def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]

candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0

while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)

for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1

print(map_[d_h][d_w])

Submission status: Time Limit Exceeded

Solution code:
#-----モジュールの読み込み-----
from collections import deque
 
#-----入力受け取り-----
H ,W = map(int,input().split())
Sa,Sb = map(int,input().split())
Ga,Gb = map(int,input().split())
maze_list = [input() for i in range(H)]
 
Sa = Sa - 1
Sb = Sb - 1
Ga = Ga - 1
Gb = Gb - 1
 
que1 = []
que1.append((Sa,Sb))
quelist = []
 
#-----全ての座標に-1の値を代入-----
 
dist = [[10**9]*W for i in range(H)]
dist[Sa][Sb] = 0
 
#-----------動作
 
count = 0
 
while len(que1) > 0:
    quelist = que1
    que1 = deque(que1)
    
   
    while  len(que1) > 0:
        i,j = que1.popleft()
        for i2, j2 in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if not (0 <= i2 <= H-1 and 0 <= j2 <= W-1):
                continue
            if maze_list[i2][j2] == "." and dist[i2][j2] > count:
                dist[i2][j2] = count
                que1.append((i2,j2))
                quelist.append((i2,j2))
    
    que2 = deque(quelist)
    count += 1
    que1 = []
    
    while len(que2) > 0:
        i,j = que2.popleft()
        for di in range(-2,3):
            for dj in range(-2,3):
                i3 = i+di
                j3 = j+dj
 
                if not (0 <= i3 <= H-1 and 0 <= j3 <= W-1):
                    continue
                if maze_list[i3][j3] == "." and dist[i3][j3] > count:
                    dist[i3][j3] = count
                    que1.append((i3,j3))
                else:
                    pass
                
 
if dist[Ga][Gb] == 10**9:
    print(-1)
else:
    print(dist[Ga][Gb])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W= map(int, input().split())
Ch,Cw= map(int, input().split())
Dh,Dw= map(int, input().split())
S = [list(input()) for i in range(H)]

#S=[['.', '.', '#', '.'],
#   ['.', '.', '#', '.'],
#   ['.', '#', '.', '.'], 
#   ['.', '#', '.', '.']]
#H,W=4,44
#Ch,Cw=1,1
#Dh,Dw=4,4

q=deque([[Ch,Cw]])
move=[[1,0],[-1,0],[0,1],[0,-1]]
move2=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],
      [-1,1],[-1,2],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
s=False
moved=[[ 0 for i in range(W)] for j in range(H)]
num=[[ 10**5 for i in range(W)] for j in range(H)]
#moved[Ch-1][Cw-1]=1
num[Ch-1][Cw-1]=0

while q:
    #print(q)
    b=q.popleft()
    moved[b[0]-1][b[1]-1]=1
    
    for m in move:
        if 1<=b[0]+m[0]<=H and 1<=b[1]+m[1]<=W and S[b[0]+m[0]-1][b[1]+m[1]-1]=='.' and moved[b[0]+m[0]-1][b[1]+m[1]-1]==0:
            #if moved[b[0]+m[0]-1][b[1]+m[1]-1]==0:
             #   moved[b[0]+m[0]-1][b[1]+m[1]-1]=1
            q.appendleft([b[0]+m[0],b[1]+m[1]])
            num[b[0]+m[0]-1][b[1]+m[1]-1]=num[b[0]-1][b[1]-1]
        
    for m2 in move2:
        if 1<=b[0]+m2[0]<=H and 1<=b[1]+m2[1]<=W and S[b[0]+m2[0]-1][b[1]+m2[1]-1]=='.' and moved[b[0]+m2[0]-1][b[1]+m2[1]-1]==0:
            #if moved[b[0]+m2[0]-1][b[1]+m2[1]-1]==0:
             #   moved[b[0]+m2[0]-1][b[1]+m[1]-1]=1
            q.append([b[0]+m2[0],b[1]+m2[1]])
            num[b[0]+m2[0]-1][b[1]+m2[1]-1]=min(num[b[0]+m2[0]-1][b[1]+m2[1]-1],num[b[0]-1][b[1]-1]+1)
           
        
#for i in range(H):
#    print(moved[i])
#for i in range(H):
#    print(num[i])

if num[Dh-1][Dw-1]==10**5:
    print(-1)
else:
    print(num[Dh-1][Dw-1])