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())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = [int(s) - 1 for s in input().split()]
Dh, Dw = [int(s) - 1 for s in input().split()]
S = [input() for _ in range(H)]

tree_check = [[0 for _ in range(W)] for _ in range(H)]
tree_check[Ch][Cw] = 1


def tree(way_start):
    while way_start:
        way = way_start.pop(0)
        y = way[0]
        x = way[1]
        if x - 1 >= 0:
            if S[y][x - 1] == '.':
                if tree_check[y][x - 1] == 0:
                    tree_check[y][x - 1] = 1
                    way_start.append([y, x - 1])
        if x + 1 < W:
            if S[y][x + 1] == '.':
                if tree_check[y][x + 1] == 0:
                    tree_check[y][x + 1] = 1
                    way_start.append([y, x + 1])
        if y - 1 >= 0:
            if S[y - 1][x] == '.':
                if tree_check[y - 1][x] == 0:
                    tree_check[y - 1][x] = 1
                    way_start.append([y - 1, x])
        if y + 1 < H:
            if S[y + 1][x] == '.':
                if tree_check[y + 1][x] == 0:
                    tree_check[y + 1][x] = 1
                    way_start.append([y + 1, x])


def warp():
    result = []
    for h in range(H):
        for w in range(W):
            if tree_check[h][w] == 1:
                for i in range(-2, 2 + 1):
                    if 0 <= h + i < H:
                        for j in range(-2, 2 + 1):
                            if 0 <= w + j < W:
                                if tree_check[h + i][w + j] == 0:
                                    if S[h + i][w + j] == '.':
                                        result.append([h + i, w + j])
    for way in result:
        x = way[1]
        y = way[0]
        tree_check[y][x] = 1
    return result


way_tree = [[Ch, Cw]]
ans = 0
while way_tree:
    tree(way_tree)
    if tree_check[Dh][Dw] == 0:
        ans += 1
        way_tree = warp()
    else:
        break

if tree_check[Dh][Dw] == 0:
    ans = -1

print(ans)

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

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
def main(H,W,ch,cw,dh,dw,S):
    q=np.zeros((3*10**7,3),dtype=np.int32)
    v=-np.ones((H,W),dtype=np.int32)
    x=[[1,0],[-1,0],[0,-1],[0,1]]
    y=[[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]]
    l,r=5*10**6,5*10**6+1
    q[l][0],q[l][1],q[l][2]=ch-1,cw-1,0
    while l<r:
        h,w,d=q[l][0],q[l][1],q[l][2]
        l+=1
        if v[h][w]<0:
            v[h][w]=d
        for k in range(4):
            i,j=x[k][0],x[k][1]
            if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] and v[h+i][w+j]<0:
                l-=1
                q[l][0],q[l][1],q[l][2]=h+i,w+j,d
        for k in range(20):
            i,j=y[k][0],y[k][1]
            if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] and v[h+i][w+j]<0:
                q[r][0],q[r][1],q[r][2]=h+i,w+j,d+1
                r+=1
    return v[dh-1][dw-1]
import sys
import numpy as np
readline=sys.stdin.buffer.readline
read=sys.stdin.buffer.read
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')
    def cc_export(f,s):
        cc.export(f.__name__,s)(f)
        return njit(f)
    main=cc_export(main,(i4,i4,i4,i4,i4,i4,i4[:,:]))
    cc.compile()
    exit()
H,W=map(int,readline().split())
ch,cw=map(int,readline().split())
dh,dw=map(int,readline().split())
S=np.array([[1 if c==ord('.') else 0 for c in readline().strip()] for i in range(H)],dtype=np.int32)
from my_module import main
print(main(H,W,ch,cw,dh,dw,S))

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = []
warp = [[10000000] * w for i in range(h)]
for i in range(h):
    s.append(input())

q = [(ch - 1, cw - 1, 0)]
qi = 0
while qi < len(q):
    i = q[qi][0]
    j = q[qi][1]
    wc = q[qi][2]
    if wc < warp[i][j]:
        warp[i][j] = wc
    else:
        qi += 1
        continue
    if i-1 >= 0 and s[i-1][j] == '.' and wc < warp[i-1][j]:
        q.append((i - 1, j, wc))
    if j-1 >= 0 and s[i][j-1] == '.' and wc < warp[i][j-1]:
        q.append((i, j - 1, wc))
    if i+1 < h and s[i+1][j] == '.' and wc < warp[i+1][j]:
        q.append((i + 1, j, wc))
    if j+1 < w and s[i][j+1] == '.' and wc < warp[i][j+1]:
        q.append((i, j + 1, wc))

    for di in range(max(i-2, 0), min(i+2, h-1)+1):
        for dj in range(max(j-2, 0), min(j+2, w-1)+1):
            if s[di][dj] == '.' and wc + 1 < warp[di][dj]:
                q.append((di, dj, wc + 1))
    qi += 1

if warp[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(warp[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


h, w = inpl()
sy, sx = inpl()
gy, gx = inpl()
sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1
maze = [str_inp() for _ in range(h)]
queue = collections.deque()

dp = [[INF] * w for i in range(h)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def bfs():
    queue.append([sx, sy])
    dp[sy][sx] = 0
    while len(queue):
        x, y = queue.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if x + j >= 0 and x + j < w and y + i >= 0 and y + i < h and maze[y + i][x + j] != "#" and dp[y + i][x + j] > dp[y][x]:
                    dp[y + i][x + j] = dp[y][x] + 1
                    queue.append([x + j, y + i])

        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]

            if next_x >= 0 and next_x < w and next_y >= 0 and next_y < h and maze[
                    next_y][next_x] != "#" and dp[next_y][next_x] > dp[y][x]:
                queue.append([next_x, next_y])
                dp[next_y][next_x] = dp[y][x]
    return dp[gy][gx]


ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans)

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 = [[-1]*(w+4)]
s.append([-1]*(w+4))
for i in range(h):
  s.append(list(input()))
  s[i+2].insert(0,-1)
  s[i+2].insert(0,-1)
  s[i+2].append(-1)
  s[i+2].append(-1)
s.append([-1]*(w+4))
s.append([-1]*(w+4))
for i in range(2,h+2):
  for j in range(2,w+2):
    if s[i][j] == '#':
      s[i][j] = -1
    else:
      s[i][j] = 10**6
s[ch+1][cw+1] = 0

stack = []
stack.append([ch+1,cw+1])
while True:
  if len(stack)==0:
    break
  st = stack.pop()
  sh = st[0]
  sw = st[1]
  if s[sh-1][sw]>s[sh][sw]:
    s[sh-1][sw] = s[sh][sw]
    stack.append([sh-1,sw])
  if s[sh][sw-1]>s[sh][sw]:
    s[sh][sw-1] = s[sh][sw]
    stack.append([sh,sw-1])
  if s[sh+1][sw]>s[sh][sw]:
    s[sh+1][sw] = s[sh][sw]
    stack.append([sh+1,sw])
  if s[sh][sw+1]>s[sh][sw]:
    s[sh][sw+1] = s[sh][sw]
    stack.append([sh,sw+1])
  shh = st[0]-2
  sww = st[1]-2
  for i in range(5):
    for j in range(5):
      if s[shh+i][sww+j] > s[sh][sw]+1:
        s[shh+i][sww+j] = s[sh][sw]+1
        stack.insert(0,[shh+i,sww+j])
      
if s[dh+1][dw+1]==10**6:
  print(-1)
else:
  print(s[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
h,w=[int(x) for x in input().split()]
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

l=[]
for i in range(h):
  s=[x for x in input()]
  l.append(s)


done=[[float('inf') for i in range(w)] for j in range(h)]
move=[[-1,0],[1,0],[0,1],[0,-1]]
m1=[]
for i in range(-2,3):
  for j in range(-2,3):
    if i==0 and j==0:
      continue
    else:
      m1.append([i,j])

def bfs(x,y):
  ans=float('inf')
  que=[[x,y,0]]

  while(que):
    # print(que)
    nx,ny,cnt = que.pop(0)
    done[ny][nx]=cnt

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)
    for dx,dy in move:
      mx,my = nx+dx,ny+dy
      if 0<=mx<w and 0<=my<h:
        if l[my][mx]=="." and (cnt<done[my][mx]):
          done[my][mx]=cnt
          que.append([mx,my,cnt])

        elif l[my][mx]=="#" and (cnt<done[my][mx]):
          for i,j in m1:
            if 0<=nx+i<w and 0<=ny+j<h and l[ny+j][nx+i]=="." and cnt<done[ny+j][nx+i]:
              done[ny+j][nx+i]=cnt+1
              que.append([nx+i,ny+j,cnt+1])
      
  return ans


ans1=bfs(cw-1,ch-1)

if ans1==float('inf'):
  print(-1)
else:
  print(ans1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import heapq

#点の数が10**5のオーダー以下で使える
#計算量はO(MlogN) M : 辺の数、N　：　頂点数
#頂点sからの各頂点への最短距離を出力
from numba import jit

@jit
def dijkstra(s, n, edge): #s:始点、n:頂点の数、edge:重み付き辺の配列（edge[i]:iから出るtuple[重み、行き先]の配列)
    INF = 10**20
    d = [INF]*n # d[i]: sと点iとの距離
    used = [True]*n #Trueは未確定
    d[s] = 0 #初期条件
    used[s] = False # 初期条件
    edge_list = []
    for a, b in edge[s]:
        heapq.heappush(edge_list, a*(10**6)+b) #heapqの中に重みと辺の抱き合わせた情報を入れる
    while len(edge_list):
        min_edge = heapq.heappop(edge_list) #まだ使われていない頂点の中から最小の重みのものを取りだす
        if not used[min_edge%(10**6)]: # 確定していたらcontinue、確定していない時のみ以下の処理を行う
            continue
        v = min_edge%(10**6) #行き先の情報を復元
        d[v] = min_edge // (10**6) #重みの情報を復元し、sとvの最短距離d[v]を更新する
        used[v] = False
        for e in edge[v]:
            if used[e[1]]: #その行き先がまだ未確定の場合
                heapq.heappush(edge_list, (e[0]+d[v])*(10**6) + e[1])
        
    return d
#d[i] : 始点から i までの距離
h, w = map(int, input().split())
edge = [[] for _ in range((h+4)*(w+4))] # edge:重み付き辺の配列（edge[i]:iから出るtuple(重み、行き先)の配列)
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
start = (ch, cw)
end = (dh, dw)
g = []
g.append([1]*(w+4))
g.append([1]*(w+4))
for i in range(h):
    s = list(input())
    tmp = [1,1]
    for j in s:
        if j == '.':
            tmp.append(0)
        else:
            tmp.append(1)
    tmp.append(1)
    tmp.append(1)
    g.append(tmp)
g.append([1]*(w+4))
g.append([1]*(w+4))
#print(g)
def pp(height, width):
    return height*(w+4)+width
d = []
for i in range(-2, 3):
    for j in range(-2,3):
        d.append((i, j))
d2 = [(-1, 0), (0, -1), (1, 0), (0,1)]

#print(d2)
for i in range(2, h+2):
    for j in range(2, w+2):
        for q in d:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((1, pp(i+x, j+y)))
        for q in d2:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((0, pp(i+x, j+y)))
#print(edge)
                
d = dijkstra(pp(ch+1, cw+1), (h+4)*(w+4), edge)

if d[pp(dh+1, dw+1)] >= 10**20:
    print(-1)
    #print(d[pp(dh+1, dw+1)])
    #print(pp(ch+1, cw+1))
    #print(pp(dh+1, dw+1))
else:
    print(d[pp(dh+1, dw+1)])

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region

regions = []
field = copy.deepcopy(S)

for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1

for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i

count = 0
d = deque()
arrived = set()
arrived_pos = set()
d.append(s_reg)
arrived.add(s_reg)

while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for i in range(len(regions)):
    if i not in arrived and i != pos:
      for pos1 in regions[i]:
        for pos2 in regions[pos]:
          hd = abs(pos1[0] - pos2[0])
          wd = abs(pos1[1] - pos2[1])
          if hd <= 2 and wd <= 2:
            if i not in arrived:
              arrived.add(i)
              d.append(i)
  count += 1
            
if g_reg not in arrived:
  print(-1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for h in range(H):
        Sh =  list(input())
        S.append(Sh)

    que = {(Ch-1,Cw-1)}
    jump_que = set()
    goal = (Dh-1, Dw-1)
    searched=set()
    jump =0

    while(True):
        while(len(que)):
            tmp = que.pop()
            if tmp ==goal:
                print(jump)

                return

            searched.add(tmp)
            nxts=get_around(S,H,W,tmp[0],tmp[1])-searched
            # print(f'nxts: {nxts}')
            que=que|nxts
            jump_nxts = get_jump_around(S, H, W, tmp[0], tmp[1]) - searched
            # print(f'jump_nxts: {jump_nxts}')
            jump_que = jump_que | jump_nxts
            # print(f'jump_que: {jump_que}')

        jump=jump+1
        que=jump_que
        jump_que = set()
        if len(que)==0:
            print('-1')
            return


def get_around(S,H,W, h,w):
    hm = h-1
    hp =h+1
    wm = w-1
    wp= w+1
    nxt=set()
    if hm>=0 and S[hm][w]=='.':
        nxt.add((hm,w))

    if hp<H and S[hp][w]=='.':

        nxt.add((hp,w))
    if wm>=0 and S[h][wm]=='.':
        nxt.add((h,wm))

    if wp<W and S[h][wp]=='.':
        nxt.add((h,wp))
    return nxt

def get_jump_around(S,H,W, h,w):
    hm = max(h-2,0)
    hp =min(h+2,H-1)
    wm = max(w-2,0)
    wp= min(w+2,W-1)
    nxt=set()
    # print(hm,hp,wm,wp)
    for h in range(hm,hp+1):
        for w in range(wm, wp + 1):
            if S[h][w]=='.':
                nxt.add((h, w))

    return nxt


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output,out)

    def test_入力例_1(self):
        input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

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 = []
for h in range(H):
    S.append(list(input()))
H -= 1;W -= 1;CH -= 1;CW -= 1;DH -= 1;DW -= 1
from collections import deque
Q = deque([[CH,CW,0]])
ans = 9999999999999999999999
able = False
while Q:
    q = Q.popleft()
    for w in range(-2,3):
        for h in range(-2,3):
            # 動かないのは処理しない
            if w == 0 and h == 0:
                pass
            else:
                # 場外判定
                # from IPython.core.debugger import Pdb; Pdb().set_trace()
                if q[0] + h >= 0 and q[0] + h <= H and q[1] + w >= 0 and q[1] + w <= W:
                    # 壁判定
                    if S[q[0]+h][q[1]+w] != '#':
                        # 徒歩判定(4パターン)
                        if (w == -1 and h == 0) or (w == 0 and h == -1) or (w == 1 and h == 0) or (w == 0 and h == 1):
                                # ゴールの場合
                                if q[0]+h == DH and q[1]+w == DW:
                                    ans = min(ans,q[2])
                                    able = True
                                    if ans == 0:
                                      print(ans)
                                      exit()
                                # 未処理の場合
                                elif S[q[0]+h][q[1]+w] == '.':
                                    S[q[0]+h][q[1]+w] = str(q[2])
                                    Q.append([q[0]+h,q[1]+w,q[2]])
                                # 処理済の場合
                                else:
                                    if int(S[q[0]+h][q[1]+w]) > q[2]:
                                        S[q[0]+h][q[1]+w] = str(q[2])
                                        Q.append([q[0]+h,q[1]+w,q[2]])
                        # ワープの場合
                        else:
                            if q[0]+h == DH and q[1]+w == DW:
                                ans = min(ans,q[2]+1)
                                able = True
                            elif S[q[0]+h][q[1]+w] == '.':
                                S[q[0]+h][q[1]+w] = str(q[2]+1)
                                Q.append([q[0]+h,q[1]+w,q[2]+1])
                            else:
                                if int(S[q[0]+h][q[1]+w]) > q[2]+1:
                                    S[q[0]+h][q[1]+w] = str(q[2]+1)
                                    Q.append([q[0]+h,q[1]+w,q[2]+1])                            
print(ans) if able else print(-1)

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

ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = []
for _ in range(h):
    s.append(input())

mtx = [[10 ** 9]*w for _ in range(h)]

cnt = -1
now = deque()
nxt = deque()
nxt.append((ch, cw))
mtx[ch][cw] = 0

while True:
    if not now:
        now = nxt
        cnt += 1
        nxt = deque()
        if not now:
            break
    h_ptr, w_ptr = now.pop()
    if h_ptr != 0:
        if s[h_ptr-1][w_ptr] == '.':
            if cnt < mtx[h_ptr-1][w_ptr]:
                mtx[h_ptr-1][w_ptr] = cnt
                now.append((h_ptr-1, w_ptr))
    if w_ptr != 0:
        if s[h_ptr][w_ptr-1] == '.':
            if cnt < mtx[h_ptr][w_ptr-1]:
                mtx[h_ptr][w_ptr-1] = cnt
                now.append((h_ptr, w_ptr-1))
    if h_ptr != h-1:
        if s[h_ptr+1][w_ptr] == '.':
            if cnt < mtx[h_ptr+1][w_ptr]:
                mtx[h_ptr+1][w_ptr] = cnt
                now.append((h_ptr+1, w_ptr))
    if w_ptr != w-1:
        if s[h_ptr][w_ptr+1] == '.':
            if cnt < mtx[h_ptr][w_ptr+1]:
                mtx[h_ptr][w_ptr+1] = cnt
                now.append((h_ptr, w_ptr+1))
    for i in range(h_ptr-2, h_ptr+3):
        for j in range(w_ptr-2, w_ptr+3):
            if 0 <= i < h and 0 <= j < w and s[i][j] == '.':
                if cnt + 1 < mtx[i][j]:
                    mtx[i][j] = cnt + 1
                    nxt.append((i, j))

ret = mtx[dh][dw]

if ret == 10 ** 9:
    print(-1)
else:
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 1e9+7

h,w = map(int,input().split())
ch,cw = map(int,input().split())  
dh,dw = map(int,input().split())
maze = [[INF]*(w+4) for _ in range(h+4)]


for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            maze[i+2][j+2] = -1

cnt = 0

maze[ch+1][cw+1] = cnt
qh,qw = deque(),deque()
qh.append(ch+1)
qw.append(cw+1)

mqh,mqw = deque(),deque()
flag = False

while True:
    while True:
        if len(qh) == 0:
            break

        nh,nw = qh.popleft(),qw.popleft()
        mqh.append(nh)
        mqw.append(nw)
        dir_h,dir_w = [1,-1,0,0],[0,0,1,-1]
        for i in range(4):
            if maze[nh+dir_h[i]][nw+dir_w[i]] == -1:
                maze[nh+dir_h[i]][nw+dir_w[i]] = cnt
                qh.append(nh+dir_h[i])
                qw.append(nw+dir_w[i])

    cnt += 1
    while True:
        if len(mqh) == 0:
            break

        nh,nw = mqh.popleft(),mqw.popleft()
        for i in range(5):
            for j in range(5):
                if maze[nh-2+i][nw-2+j] == -1:
                    maze[nh-2+i][nw-2+j] = cnt
                    qh.append(nh-2+i)
                    qw.append(nw-2+j)
                
    if maze[dh+1][dw+1] != -1:
        flag = True
        break

    if len(qh) == 0:
        break

if flag:
    print(maze[dh+1][dw+1])
else:
    print(-1)

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())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  while len(q):
    y,x=q.popleft()
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
            elif D[ny][nx]>D[y][x]+1:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

def main():
  walks=[(-1,0),(1,0),(0,-1),(0,1)]
  warps=[(-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)]
  h,w=map(int,input().split())
  ch,cw=map(int,input().split())
  dh,dw=map(int,input().split())

  inf=10*7
  
  maze=[list(input()) for _ in range(h)]

  que=[(0,ch,cw)]
  visited={(ch,cw):0}
  
  while len(que)>0:
    wt,eh,ew=heappop(que)
    #print(wt,eh,ew,len(que),len(visited),visited[(2,1)] if (2,1) in visited else 'ii')
    if (eh,ew)==(dh,dw):
      return wt
    for walkh,walkw in walks:
      th=eh+walkh
      tw=ew+walkw
      if (th,tw)==(dh,dw):
        return wt
      if th<1 or th>h or tw<1 or tw>w:
        continue
      if (th,tw) in visited and visited[(th,tw)]<=wt:
        continue
      #print(th,tw,eh,ew,wt,maze[th-1][tw-1])
      if maze[th-1][tw-1]=='.':
        heappush(que,(wt,th,tw))
        visited[(th,tw)]=wt
    for warph,warpw in warps:
      th=eh+warph
      tw=ew+warpw
      if th<1 or th>h or tw<1 or tw>w:
        continue
      if (th,tw) in visited and visited[(th,tw)]<=wt+1:
        continue
      #print(th,tw,eh,ew,wt,maze[th-1][tw-1],'x')
      if maze[th-1][tw-1]=='.':
        heappush(que,(wt+1,th,tw))
        visited[(th,tw)]=wt+1
  
  return -1

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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())
T = [list(input()) for _ in range(H)]

for i in range(H):
  for j in range(W):
    if T[i][j] == ".":
      T[i][j] = float('inf')

def dfs(y, x, prey, prex, c):
  T[y][x] = c
  for dy in range(-2, 3):
    for dx in range(-2, 3):
      ny = y + dy
      nx = x + dx
      if 0 <= ny < H and 0 <= nx < W and T[ny][nx] != "#" and T[ny][nx] > c and (prey != ny or prex != nx):
        if abs(dy) + abs(dx) <= 1:
          dfs(ny, nx, y, x, c)
        else:
          dfs(ny, nx, y, x, c+1)

dfs(ch, cw, -1, -1, 0)

if T[dh][dw] == float('inf') or T[dh][dw] == "#":
  print(-1)
else:
  print(T[dh][dw])