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, = 4, 4
# CH, CW = 1, 1
# DH, DW = 4, 4
#
# ARR = [
#     "..#.",
#     "..#.",
#     ".#..",
#     ".#.."
# ]
#
#
#
# H,W = 4, 4
# CH, CW = 1, 4
# DH, DW = 4, 1
# ARR = [
#     ".##.",
#     "####",
#     "####",
#     ".##."
# ]
#
#
#
# H,W = 4, 4
# CH,CW = 2, 2
# DH,DW = 3, 3
# ARR = [
#     "....",
#     "....",
#     "....",
#     "...."
# ]
#
#
# H,W = 4, 5
# CH,CW = 1, 2
# DH,DW = 2, 5
#
# ARR = [
#     "#.###",
#     "####.",
#     "#..##",
#     "#..##"
# ]
#
#

H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
ARR = []

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




def calculate(h, w, ch, cw, dh, dw, arr):

    status = [[-1 for j in range(w)] for i in range(h)]

    q = deque()

    q.append((ch - 1, cw - 1))
    status[ch - 1][cw - 1] = 0

    while len(q) > 0:
        currentY, currentX = q.popleft()
        childrens = [(currentY, currentX - 1), (currentY + 1, currentX), (currentY, currentX + 1),
                     (currentY - 1, currentX)]

        for child in childrens:
            childY, childX = child
            if childX >= 0 and childX < w and childY >= 0 and childY < h:
                if arr[childY][childX] == ".":
                    if status[childY][childX] == -1:
                        q.append((childY, childX))
                        status[childY][childX] = status[currentY][currentX]
                    else:
                        if status[childY][childX] > status[currentY][currentX]:
                            status[childY][childX] = status[currentY][currentX]
                            q.append((childY, childX))

        for i in range(-2, 3):
            for j in range(-2, 3):
                childY = currentY + i
                childX = currentX + j
                if (childY, childX) in childrens:
                    continue

                if childX >= 0 and childX < w and childY >= 0 and childY < h:
                    if arr[childY][childX] == ".":
                        if status[childY][childX] == -1:
                            status[childY][childX] = (status[currentY][currentX] + 1)
                            q.append((childY, childX))
                        else:
                            if status[childY][childX] > (status[currentY][currentX] + 1):
                                status[childY][childX] = (status[currentY][currentX] + 1)
                                q.append((childY, childX))
    print(status[dh-1][dw-1])
calculate(H,W,CH,CW,DH,DW,ARR)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch+=-1
    Cw+=-1
    Dh,Dw = map(int,input().split())
    Dh+=-1
    Dw+=-1
    S = [None for i in range(H)]
    
    for i in range(H):
        S[i] = input()
        
    ans=0
    visited = [[False for i in range(W)] for j in range(H)]
    walk_deque = deque()
    walk_deque.append((Ch,Cw))
    visited[Ch][Cw]=True
    while(1):
        new_visited = []
        while(len(walk_deque) != 0):
            Ph,Pw = walk_deque.popleft()
            new_visited.append([Ph,Pw])
            #print(Ph,Pw)
            if Ph==Dh and Pw==Dw:
                print(ans)
                return
            for i in range(4):
                tmph = Ph+dy[i]
                tmpw = Pw+dx[i]
                if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                    if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                        walk_deque.append((tmph,tmpw))
                        visited[tmph][tmpw]=True

        #print("warp")
        for h,w in new_visited:
            for x in [-2,-1,0,1,2]:
                for y in [-2,-1,0,1,2]:
                    tmph = h+y
                    tmpw = w+x
                    if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                        if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                            walk_deque.append((h+y,w+x))
                            visited[h+y][w+x]=True
        ans+=1
        if len(walk_deque)==0:
            print(-1)
            return
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch+=-1
    Cw+=-1
    Dh,Dw = map(int,input().split())
    Dh+=-1
    Dw+=-1
    S = [None for i in range(H)]
    
    for i in range(H):
        S[i] = input()
        
    ans=0
    visited = [[False for i in range(W)] for j in range(H)]
    walk_deque = deque()
    walk_deque.append((Ch,Cw))
    visited[Ch][Cw]=True
    while(1):
        while(len(walk_deque) != 0):
            Ph,Pw = walk_deque.popleft()
            #print(Ph,Pw)
            if Ph==Dh and Pw==Dw:
                print(ans)
                return
            for i in range(4):
                tmph = Ph+dy[i]
                tmpw = Pw+dx[i]
                if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                    if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                        walk_deque.append((tmph,tmpw))
                        visited[tmph][tmpw]=True
        #print("warp")
        old_visited = deepcopy(visited)
        for h in range(H):
            for w in range(W):
                if old_visited[h][w]:
                    for x in [-2,-1,0,1,2]:
                        for y in [-2,-1,0,1,2]:
                            tmph = h+y
                            tmpw = w+x
                            if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                                if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                                    walk_deque.append((h+y,w+x))
                                    visited[h+y][w+x]=True
        ans+=1
        if len(walk_deque)==0:
            print(-1)
            return
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1, 0))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x, s = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or score[(y+dy, x+dx)] > s:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx, s))
          score[(y+dy, x+dx)] = s
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or score[(y+dy, x+dx)] > s+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx, s+1))
          score[(y+dy, x+dx)] = s+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or score[(y+dy, x+dx)] > score[(y, x)]:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or score[(y+dy, x+dx)] > score[(y, x)]+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  s = score[(y, x)]
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > s):
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = s
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > s+1):
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = s+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
m_d = list()    # 魔法移動距離
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# BFS探索用キュー
from collections import deque
q_a = deque() # 徒歩
q_b = deque() # ワープ

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q_a.append([si,sj])

while (len(q_a)>0):
    i, j = ij = q_a.popleft()
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            q_b.append(ij)
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q_a.append([ni,nj])

    if len(q_a) == 0:
        while (len(q_b)>0):
            i, j = q_b.popleft()
            d = dist[i][j]
            for di, dj in m_d:
                ni, nj = di+i, dj+j
                if (S[ni][nj]=='#'):
                    continue # 壁
                if (dist[ni][nj]<=d):
                    continue # 探索済みコスト以上
                dist[ni][nj] = d+1
                q_a.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m_d = list()    # 魔法移動距離
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# BFS探索用キュー
from collections import deque
q_a = deque() # 徒歩
q_b = deque() # ワープ

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q_a.append([si,sj])

while (len(q_a)>0):
    i, j = ij = q_a.popleft()
    q_b.append(ij)
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q_a.append([ni,nj])

    if len(q_a) == 0:
        while (len(q_b)>0):
            i, j = q_b.popleft()
            d = dist[i][j]
            for di, dj in m_d:
                ni, nj = di+i, dj+j
                if (S[ni][nj]=='#'):
                    continue # 壁
                if (dist[ni][nj]<=d):
                    continue # 探索済みコスト以上
                dist[ni][nj] = d+1
                q_a.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > score[(y, x)]):
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > score[(y, x)]+1):
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
m_d = list()    # 魔法移動距離
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append([si,sj])

while (len(q)>0):
    i, j = q.popleft()
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q.appendleft([ni,nj])

    for di, dj in m_d:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d+1
        q.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m_d = list()    # 魔法移動距離
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q.popleft()
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q.appendleft((ni,nj))

    for di, dj in m_d:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d+1
        q.append((ni,nj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
d_c = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) == (0,0):
            continue
        elif (i,j) in [(-1,0),(0,-1),(1,0),(0,1)]:
            d_c += [(i,j,0)]   # 歩くコスト
        else:
            d_c += [(i,j,1)]   # 魔法コスト

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    for di, dj, c in d_c:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d+c
        if c == 0:
            q.appendleft((ni,nj))
        else:
            q.append((ni,nj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in (d_a+[(0,0)]):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    close_wall = False
    # 移動Aによるコスト
    for di, dj in d_a:
        di, dj = di+i, dj+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (S[di][dj]=='#'):
            close_wall = True
            continue # 壁
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 壁際ならば移動Bによるコストを探索
    if close_wall:
        for di, dj in d_b:
            di, dj = di+i, dj+j
            if (S[di][dj]=='#'):
                continue # 壁
            if (dist[di][dj]<=d):
                continue # 探索済みコスト以上
            dist[di][dj] = d+1
            q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = ["" for _ in range(H)]
for i in range(H):
  Shw[i] = input()

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or (score[(y+dy, x+dx)] and score[(y+dy, x+dx)] > score[(y, x)]):
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > score[(y, x)]+1):
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in (d_a+[(0,0)]):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for di, dj in d_a:
        di, dj = di+i, dj+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (S[di][dj]=='#'):
            continue # 壁
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for di, dj in d_b:
        di, dj = di+i, dj+j
        if (S[di][dj]=='#'):
            continue # 壁
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in (d_a+[(0,0)]):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(len(dist)):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(len(dist[0])):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for di, dj in d_a:
        di, dj = di+i, dj+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for di, dj in d_b:
        di, dj = di+i, dj+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if not((i,j) in d_a) and ((i,j) != (0,0)):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(len(dist)):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(len(dist[0])):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        di, dj = d_b[v][0]+i, d_b[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# D - Wizard in Maze
def get_index(s):
	return int(s) - 1


def search_nearby(h, w):
# 上下左右に隣接するマスを探索
	search(h + 1, w, False)
	search(h - 1, w, False)
	search(h, w + 1, False)
	search(h, w - 1, False)


def search_using_warp(h, w):
  # ワープ魔法で移動できるマスを探索
  for i in range(-2, 3):
    search(h - 2, w + i)
    search(h + 2, w + i)

  for i in range(-2, 3):
    if i != 0:
      search(h - 1, w + i)
      search(h + 1, w + i)

  search(h, w + 2)
  search(h, w - 2)


def search(h, w, is_using_warp = True):
  global is_reached
  global que
  global next_que

  if can_reach(h, w):
	  is_reached[h][w] = True
	  next_que.append([h, w])

	  if not is_using_warp:
	    que.append([h, w])


def can_reach(h, w):
	global H
	global W
	global maze

	if h < 0 or h >= H or w < 0 or w >= W:
		return False
	elif maze[h][w] == '#':
		return False
	elif is_reached[h][w]:
		return False
	else:
		return True


from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(get_index, input().split())
Dh, Dw = map(get_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

next_que = deque()
next_que.append([Ch, Cw])
mp = 0

while len(next_que) > 0:
  que = copy.deepcopy(next_que)

	# コストiで到達可能なマスを列挙
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_nearby(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

  que = copy.deepcopy(next_que)
  next_que.clear()
  mp += 1

	# コストiで到達可能なマスを列挙
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_using_warp(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def solve(h, w, ch, cw, dh, dw, s):
    G = [[0]*w for r in range(h)]
    label = 0
    for r in range(h):
        for c in range(w):
            if (s[r][c] == '.') and (G[r][c] == 0):
                label += 1
                que = deque([(r, c)])
                G[r][c] = label
                while que:
                    cr, cc = que.popleft()
                    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        nr, nc = cr+dr, cc+dc
                        if (0 <= nr < h) and (0 <= nc < w) and (s[nr][nc] == ".") and (G[nr][nc] == 0):
                            G[nr][nc] = label
                            que.append((nr, nc))

    sr, sc = ch-1, cw-1
    tr, tc = dh-1, dw-1

    neighbors = [(dr, dc) for dc in range(-2, 3) for dr in range(-2, 3) if abs(dr) + abs(dc) > 0]
    used = [[(s[r][c] == "#") for c in range(w)] for r in range(h)]
    que = deque([(sr, sc, 0)])
    label_dist_mapping = [-1] * (label + 1)
    used[sr][sc] = True
    label_dist_mapping[G[sr][sc]] = 0
    while que:
        cr, cc, n = que.popleft()
        if (cr == tr) and (cc == tc):
            return n
        for dr, dc in neighbors:
            nr, nc = cr+dr, cc+dc
            if (0 <= nr < h) and (0 <= nc < w) and not used[nr][nc]:
                used[nr][nc] = True
                d = label_dist_mapping[G[nr][nc]]
                if (G[nr][nc] == G[cr][cc]) or (n == d): # 同一グループ
                    que.appendleft((nr, nc, n))
                else:
                    label_dist_mapping[G[nr][nc]] = n + 1
                    que.append((nr, nc, n+1))
    return -1

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
print(solve(h, w, ch, cw, dh, dw, s))