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 heapq

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

def bfs(ch,cw):
    q = []#queue.Queue()
    S[ch][cw] = 0
    heapq.heappush(q,(S[ch][cw],[ch,cw]))
    while q:
        p = heapq.heappop(q)[1]
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                    
            
    return 
        
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 = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

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,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 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,(ux,uy) = hpp(q)
    if (ux,uy)==goal:
        break
#     print(ux,uy, num, prv)
    for xx,yy,vv in zip(dx,dy,vvs):
        x = ux+xx
        y = uy+yy
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue            
        if seen[x*w+y] is None or seen[x*w+y]>num:
            seen[x*w+y] = num
            hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  if (x,y)==(gh-1,gw-1):
    print(d[gh-1][gw-1])
    break
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
      d[nx][ny]=d[x][y]
      q.append((nx,ny))
  for i in range(5):
    for j in range(5):
      nx=x+wx[i]
      ny=y+wy[j]
      if not(0<=nx<h and 0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
else:print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

diffs = [(-1, 0), (0, -1), (0, 1), (1, 0)]

h, w = map(int, input().split())
start_point = tuple(map(lambda x: int(x) - 1, input().split()))
goal_point = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [input() for _ in range(h)]

counts = [[-1] * w for _ in range(h)]

counts[start_point[0]][start_point[1]] = 0
point_queue = deque([start_point])

while point_queue:
    connected_queue = deque()
    while point_queue:
        curr_h, curr_w = point_queue.pop()
        connected_queue.append((curr_h, curr_w))

        for diff_h, diff_w in diffs:
            next_h = curr_h + diff_h
            next_w = curr_w + diff_w

            if not (0 <= next_h < h and 0 <= next_w < w):
                continue

            if maze[next_h][next_w] == '#':
                continue

            if (next_h, next_w) == goal_point:
                print(counts[curr_h][curr_w])
                exit(0)

            if counts[next_h][next_w] != -1:
                continue

            counts[next_h][next_w] = counts[curr_h][curr_w]
            point_queue.append((next_h, next_w))
            connected_queue.append((next_h, next_w))

    while connected_queue:
        curr_h, curr_w = connected_queue.pop()
        for diff_h in range(-2, 3):
            for diff_w in range(-2, 3):
                next_h = curr_h + diff_h
                next_w = curr_w + diff_w

                if not (0 <= next_h < h and 0 <= next_w < w):
                    continue

                if maze[next_h][next_w] == '#':
                    continue

                if (next_h, next_w) == goal_point:
                    print(counts[curr_h][curr_w] + 1)
                    exit(0)

                if counts[next_h][next_w] != -1:
                    continue

                counts[next_h][next_w] = counts[curr_h][curr_w] + 1
                point_queue.append((next_h, next_w))

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

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.append([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        cnt = 0
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1 and cnt <= 10:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw
                    cnt += 1

    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

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

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
while queue:
    y, x,wapu = queue.popleft()
    if dist[y][x]<wapu:
      continue
    dist[y][x] = wapu
    for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue       
            else:
                 new_wapu= wapu +1
            if new_wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = new_wapu
                queue.append([new_y, new_x,new_wapu])

ans = dist[dh-1][dw-1]
if ans == inf:
  print(-1)
else:
  print(dist[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (-2, -1, 0, 1, 2)
    ry = (-2, -1, 0, 1, 2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        cost += 1
        for di in rx:
            x = px + di
            if x >= h or x < 0:
                continue
            sx = s[x]
            dpx = dp[x]
            for dj in ry:
                y = py + dj
                if y >= w or y < 0 or sx[y] == "#":
                    continue
                if dpx[y] > cost:
                    dpx[y] = cost
                    heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""連続する場所をそれぞれ付番
それぞれの領域からワープで飛べる先をリストで保存
いる場所から順に0, 1, 2と幅優先"""
H, W = [int(i) for i in input().split()]
Ci, Cj = [int(i)-1 for i in input().split()]
Di, Dj = [int(i)-1 for i in input().split()]
S = []
for i in range(H):
    S.append([i for i in input()])


def append_label_4(i, j, n):
    if S[i][j] != ".":
        return n
    labeling_list = [[i, j]]
    while labeling_list:
        i, j = labeling_list[-1]
        S[i][j] = n
        labeling_list = labeling_list[:-1]
        if i != 0 and S[i-1][j] == ".":
            labeling_list.append([i-1, j])
            S[i-1][j] = n
        if i != H-1 and S[i+1][j] == ".":
            labeling_list.append([i+1, j])
            S[i+1][j] = n
        if j != 0 and S[i][j-1] == ".":
            labeling_list.append([i, j-1])
            S[i][j-1] = n
        if j != W-1 and S[i][j+1] == ".":
            labeling_list.append([i, j+1])
            S[i][j+1] = n
    return n+1


# ラベリング
label = 0
for i in range(H):
    for j in range(W):
        label = append_label_4(i, j, label)
L = label
# ワープ関係
warpable_label_bits = []
for label in range(L):
    warpable_temp = [0]*L
    for i in range(H):
        for j in range(W):
            if S[i][j] == label:
                for ii in range(max(0, i-2), min(H-1, i+2)+1):
                    for jj in range(max(0, j-2), min(W-1, j+2)+1):
                        if S[ii][jj] != label and S[ii][jj] != '#':
                            warpable_temp[S[ii][jj]] = 1
    warpable_label_bits.append(warpable_temp)

warptimes = [-1]*L
start_label = S[Ci][Cj]
warptimes[start_label] = 0
for hops in range(L):
    for label in range(L):
        if warptimes[label] == hops:
            for ll in range(L):
                if warpable_label_bits[label][ll] == 1:
                    warptimes[ll] = hops+1

goal_label = S[Di][Dj]
print(warptimes[goal_label])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from heapq import *
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
        f(i,j,i+1,j+1)
        f(i,j,i+2,j+1)
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j)
        f(i,j,i,j+2)
        
        f(i,j,i-1,j+1)
        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)

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())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = [[ch,cw,0]]
while len(pos)>0:
  x, y, hop = pos.pop(0)
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
    
  maze[x][y] = 2
  
  flag = 0
  if maze[x-1][y] <2:
    pos.append([x-1,y,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        flag =1
        pos.append([x-2,y,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        flag =1
        pos.append([x-2,y+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        flag =1
        pos.append([x-2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        flag =1
        pos.append([x-2,y-1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        flag =1
        pos.append([x-2,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        flag =1
        pos.append([x+2,y,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        flag=1
        pos.append([x+2,y-1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        flag=1
        pos.append([x+2,y-2,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        flag=1
        pos.append([x+2,y+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        flag=1
        pos.append([x+2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        flag=1
        pos.append([x,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        flag=1
        pos.append([x+1,y-2,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        flag=1
        pos.append([x-1,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        flag=1
        pos.append([x,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        flag=1
        pos.append([x+1,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        flag=1
        pos.append([x-1,y+2,hop+1])
    except:
      pass
    
    
    if maze[x-1][y-1] <2:
      flag=1
      pos.append([x-1,y-1,hop+1])
    if maze[x-1][y+1] <2:
      flag=1
      pos.append([x-1,y+1,hop+1])
    if maze[x+1][y-1] <2:
      flag=1
      pos.append([x+1,y-1,hop+1])
    if maze[x+1][y+1] <2:
      flag=1
      pos.append([x+1,y+1,hop+1])
    
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

def search(cost, sx, sy):
    # ある地点からジャンプ無しで行ける範囲を探索

    que = deque()
    que.append((sx,sy))

    reached = []

    while que:
        x,y = que.popleft()

        # 訪れた場所リスト
        reached.append((x,y))

        if cost_map[y][x] <= cost:
            continue
        cost_map[y][x] = cost

        for x2, y2 in neighbors4(x,y):
            if x2<0 or x2>=w or y2<0 or y2>=h:
                continue
            if grid_s[y2][x2] == ".":
                que.append((x2, y2))
    
    return reached

def jump(cost, x, y):
    if cost >= cost_map[y][x]:
        return
    reached = search(cost, x, y)
    
    # ゴールに到達したらおわり
    if cost_map[dh][dw] != INF:
        print(cost_map[dh][dw])
        exit()
    
    # 1回ジャンプする
    for x,y in reached:
        for y2 in range(max(0, y-2), min(h, y+3)):
            for x2 in range(max(0, x-2), min(w, x+3)):
                if abs(x-x2) + abs(y-y2) < 2:
                    continue
                if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                    heappush(jump_heap, (cost+1, x2, y2))

def main():
    global h,w,dh,dw,grid_s,cost_map, jump_heap,INF
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w = get_nums_l()
    ch,cw = get_nums_l()
    dh,dw = get_nums_l()

    # 0-originに変換
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1

    grid_s = []
    for i in range(h):
        grid_s.append(input())
    
    cost_map = [[INF] * w for _ in range(h) ]

    jump_heap = [(0, cw, ch)]

    while jump_heap:
        cost, x, y = heappop(jump_heap)
        
        if cost >= cost_map[y][x]:
            continue
        reached = search(cost, x, y)
        
        # ゴールに到達したらおわり
        if cost_map[dh][dw] != INF:
            print(cost_map[dh][dw])
            exit()
        
        # 1回ジャンプする
        for x,y in reached:
            for y2 in range(max(0, y-2), min(h, y+3)):
                for x2 in range(max(0, x-2), min(w, x+3)):
                    if abs(x-x2) + abs(y-y2) < 2:
                        continue
                    if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                        heappush(jump_heap, (cost+1, x2, y2))
    
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys, threading
 
threading.stack_size(2**27)
sys.setrecursionlimit(10**5 + 100)

def main():
    def is_sosed(h1, w1):
        if h1 > 0:
            if (dp[h1-1][w1] == -1):
                if (m[h1-1][w1] == '.'):
                    dp[h1-1][w1] = dp[h1][w1]
                    is_sosed(h1-1, w1)
                else:
                    dp[h1-1][w1] = 10000
        if w1 > 0:
            if (dp[h1][w1-1] == -1):
                if (m[h1][w1-1] == '.'):
                    dp[h1][w1-1] = dp[h1][w1]
                    is_sosed(h1, w1-1)
                else:
                    dp[h1][w1-1] = 10000
        if h1 < h - 1:
            if (dp[h1+1][w1] == -1):
                if (m[h1+1][w1] == '.'):
                    dp[h1+1][w1] = dp[h1][w1]
                    is_sosed(h1+1, w1)
                else:
                    dp[h1+1][w1] = 10000
        if w1 < w - 1:
            if (dp[h1][w1+1] == -1):
                if (m[h1][w1+1] == '.'):
                    dp[h1][w1+1] = dp[h1][w1]
                    is_sosed(h1, w1+1)
                else:
                    dp[h1][w1+1] = 10000

    def find_warps(now):
        if dp[dh-1][dw-1] > -1:
            return True
        fl = True
        for i in range(h):
            for j in range(w):
                if dp[i][j] == now:
                    for k in range(max(0, i-2), min(h, i+3)):
                        for p in range(max(0, j-2), min(w, j+3)):
                            if dp[k][p] == -1:
                                if m[k][p] == '.':
                                    fl = False
                                    dp[k][p] = dp[i][j] + 1
                                    if dp[dh-1][dw-1] > -1:
                                        return True
                                    stack.append([k, p])
                                else:
                                    dp[k][p] = 10000
        return fl

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    m = [[] for i in range(h)]
    dp = [[-1]*w for i in range(h)]
    for i in range(h):
        m[i] = input()
    dp[ch-1][cw-1] = 0
    stack = [[ch-1, cw-1]]
    now = 0
    fl = False
    while dp[dh-1][dw-1] == -1:
        while stack:
            h11, w11 = stack.pop()
            is_sosed(h11, w11)
            if dp[dh-1][dw-1] > -1:
                break
        fl = find_warps(now)
        now += 1
        if fl:
            break
    print(dp[dh-1][dw-1])

t = threading.Thread(target=main)
t.start()
t.join()

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10
H, W = [int(i) for i in input().split(" ")]
Ch, Cw = [int(i) + 1 for i in input().split(" ")]
Dh, Dw = [int(i) + 1 for i in input().split(" ")]
S = [[False for i in range(W + 4)], [False for i in range(W + 4)]]
for i in range(H):
    S.append([False, False] + [j == '.' for j in input()] + [False, False])
S += [[False for i in range(W + 4)], [False for i in range(W + 4)]]


def check(h, w, island_num):
    assert S[h][w]
    block[h][w] = island_num
    if S[h - 1][w] and block[h - 1][w] == -1:
        check(h - 1, w, island_num)
    if S[h + 1][w] and block[h + 1][w] == -1:
        check(h + 1, w, island_num)
    if S[h][w - 1] and block[h][w - 1] == -1:
        check(h, w - 1, island_num)
    if S[h][w + 1] and block[h][w + 1] == -1:
        check(h, w + 1, island_num)


block = []
for i in range(H + 4):
    block.append([-1 for j in range(W + 4)])

island_num = 0

for h in range(H + 4):
    for w in range(W + 4):
        if S[h][w] and block[h][w] == -1:
            check(h, w, island_num)
            island_num += 1


neighbor = {}
for island in range(island_num):
    neighbor[island] = set()


for h in range(2, H + 2):
    for w in range(2, W + 2):
        if block[h][w] != -1:
            for y in range(h - 2, h + 3):
                for x in range(w - 2, w + 3):
                    if block[y][x] != -1 and block[h][w] != block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start = block[Ch][Cw]
goal = block[Dh][Dw]
assert start != -1
assert goal != -1


dist = [INF for i in range(island_num)]
dist[start] = 0

nexts = [start]
while True:
    _nexts = []
    for n in nexts:
        for neigh in neighbor[n]:
            assert neigh != -1
            if dist[neigh] > dist[n] + 1:
                _nexts.append(neigh)
                dist[neigh] = dist[n] + 1
    nexts = list(set(_nexts))
    if len(nexts) == 0:
        break

if dist[goal] == INF:
    print(-1)
else:
    print(dist[goal])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, readline().split())
C_h, C_w = map(int, readline().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, readline().split())
D_h -= 1
D_w -= 1
S = []
for _ in range(H):
    row = list(readline().decode())
    S.append(row)
if S[D_h][D_w] == '#' or S[C_h][C_w] == '#':
    print(-1)
else:
    queue = [(0, (C_h, C_w))]
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
sx,sy=mp()
gx,gy=mp()
g=[]
g.append("#"*(w+4))
g.append("#"*(w+4))
c=[[0]*(w+4)  for i in range(h+4)]
for i in range(h):
    g.append("##"+input()+"##")
g.append("#"*(w+4))
g.append("#"*(w+4))
num=0
for i in range(2,h+2):
    for j in range(2,w+2):
        if g[i][j]=="." and c[i][j]==0:
            num+=1
            que=deque([])
            que.append([i,j])
            while len(que):
                q=que.pop()
                c[q[0]][q[1]]=num
                for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                    if g[q[0]+x][q[1]+y]=="." and c[q[0]+x][q[1]+y]==0:
                        que.append([q[0]+x,q[1]+y])

tree=[[0]*(num+1) for i in range(num+1)]
for i in range(2,h+2):
    for j in range(2,w+2):
        if g[i][j]==".":
            nnum=c[i][j]
            for x,y in [[-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,0],[0,1],[0,2],[1,-2],[1,-1],[1,0],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]:
                if c[i+x][j+y]!=0 and c[i+x][j+y]!=nnum:
                    tree[nnum][c[i+x][j+y]]=1
                    tree[c[i+x][j+y]][nnum]=1

start=c[sx+1][sy+1]
goal=c[gx+1][gy+1]
que=deque([])
if start==goal:
    print(0)
    exit()
for i in range(num+1):
    if tree[start][i]!=0:
        que.append([i,1])
while len(que):
    q=que.popleft()
    if q[0]==goal:
        print(q[1])
        exit()
    for i in range(num+1):
        if tree[q[0]][i]!=0:
            que.append([i,q[1]+1])
print(-1)