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:
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
from collections import defaultdict
seen=defaultdict(int)
gx-=1;gy-=1
hq=[(nx-1)*w+ny-1]
SIZE=h*w
while hq:
    d=heappop(hq)
    c,x,y=d//(h*w),d%(h*w)//w,d%(h*w)%w
    if seen[w*x +y]:continue
    seen[w*x +y]=1
    if x==gx and y==gy:print(c);exit()
    if x and seen[w*(x-1)+y]==0 and maze[x-1 ][y]!="#":
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and  seen[w*x+y-1]==0 and maze[x][y-1]!="#":
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and  seen[w*(x+1)+y]==0 and maze[x+1][y]!="#":
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and seen[w*x+y+1 ]==0 and maze[x][y+1]!="#":
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]=="."and  seen[w*i + j ]==0:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)

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):
    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
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)
        f(i,j,i-2,j)

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

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()))
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

from collections import deque
maze = []
for i in range(H):
    maze.append(list(input()))
times = [[10000000]*W for i in range(H)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
que = deque([])
que.append((Ch, Cw))
times[Ch][Cw] = 0
cnt = 0
flag = 0
while flag==0:
    loc = deque([])
    while que:
        p = que.popleft()
        loc.append(p)
        if p[0] == Dh and p[1] == Dw:
            times[Dh][Dw] = cnt
            flag = 1
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==10000000):
                que.append((nh, nw))
                times[nh][nw] = cnt
    que = deque([])
    while loc:
        p = loc.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                nh = p[0] + i
                nw = p[1] + j
                if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==10000000):
                    que.append((nh, nw))
    if len(que)==0:
        break
    cnt += 1

if times[Dh][Dw] == 10000000:
    print(-1)
else:
    print(times[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind:
    def __init__(self, n):
        self.setSize = [1] * n
        self.numSets = n
        self.rank = [0] * n
        self.p = [i for i in range(n)]
    def findSet(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.findSet(self.p[i])
            return self.p[i]
    def isSameSet(self, i, j):
        return self.findSet(i) == self.findSet(j)
    def unionSet(self, i, j):
        if not self.isSameSet(i, j):
            self.numSets -= 1
            x = self.findSet(i)
            y = self.findSet(j)
            if self.rank[x] > self.rank[y]:
                self.p[y] = x
                self.setSize[x] += self.setSize[y]
            else:
                self.p[x] = y
                self.setSize[y] += self.setSize[x]
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1
    def numDisjointSets(self):
        return self.numSets
    def sizeOfSet(self, i):
        return self.setSize[self.findSet(i)]


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()]
A = [input() for i in range(h)]
uf = UnionFind(h*w)
twoonemap = dict()
onetwomap = dict()
counter = 0
for i in range(h):
    for j in range(w):
        twoonemap[(i,j)] = counter
        onetwomap[counter] = (i,j)
        counter += 1
for i in range(h):
    for j in range(w):
        if A[i][j] == '.':
            if j+1 < w and A[i][j+1] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i, j+1)])
            if i+1 < h and A[i+1][j] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i+1, j)])

source_set = uf.findSet(twoonemap[(ch, cw)])
target_set = uf.findSet(twoonemap[(dh, dw)])
if source_set == target_set:
    print(0)
    # now find the distance between the disjoint component
else:
    g = defaultdict(set)
    for i in range(h):
        for j in range(w):
            if A[i][j] == '.':
                first_set = uf.findSet(twoonemap[(i,j)])
                for k1 in range(i-2, i+3):
                    for k2 in range(j-2, j+3):
                        if 0<= k1 < h and 0<= k2 < w and A[k1][k2] == '.':
                            second_set = uf.findSet(twoonemap[(k1,k2)])
                            if first_set != second_set:
                                g[first_set].add(second_set)
                                g[second_set].add(first_set)
    visited = [False] * (h*w) 
    dist = [-1] *  (h*w)
    q = deque()
    q.append(source_set)  # set
    dist[source_set] = 0
    while q:
        w = q.popleft()
        for v in g[w]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
                dist[v] = dist[w] + 1
    print(dist[target_set])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh*(W+4)+sw] = 0
d.append(sh*(W+4)+sw)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.append(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

def explore(C, D):
    queue = deque([[C[0]-1, C[1]-1]])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if S[n_y][n_x] == '.':
                    if mv_n > mv_cur:
                        maze_visited[n_y][n_x] = mv_cur
                        queue.append([n_y, n_x])
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if S[n_y][n_x] == '.':
                        if mv_n > mv_cur + 1:
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append([n_y, n_x])
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

S = [list(input()) for i in range(H)]

maze_visited = [[math.inf] * W for i in range(H)]

explore(C,D)

if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 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=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue = deque([[ch-1, cw-1]])
while queue:  
  x,y=queue.popleft()
  for i,j in [[1,0],[-1,0],[0,1],[0,-1],[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=temp[x][y]:
      continue
    if (i==1 and j==0) or (i==-1 and j==0) or (i==0 and j==1) or (i==0 and j==-1):
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y])
    else:
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y]+1)
    queue.append([xtemp,ytemp])
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
 
# sys.setrecursionlimit(5000)
 
n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]
 
def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)
 
H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)
 
T = [u"#"*(W+4)] * 2
for s in S:
    T.append("##" + s[0] + "##")
T += [u"#"*(W+4)] * 2
 
H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1
 
deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()
 
cnt = 0
 
memo = array2(H, W, 10**6)
memo[Ch][Cw] = 0
 
for i in range(10**6):
    #pprint(T)
    #pprint(memo)
    #print("-"*30 + "\n")
 
    if len(deq1) == 0:
        print(-1)
        exit(0)
 
    while len(deq1) > 0:
        h, w = deq1.pop()
 
        if h == Dh and w == Dw:
            print(i)
            exit(0)
 
        def sch(x, y, i):
            #print(x, y, T[x][y])
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))
 
        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)
 
    for j in range(H):
        for k in range(W):
            if memo[j][k] == i:
                for l in range(-2, 3):
                    for m in range(-2, 3):
                        if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                            memo[j+l][k+m] = i + 1
                            deq2.append((j+l, k+m))
 
    deq1 = deq2
    deq2 = deque()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [int(i)-1 for i in input().split()]
D = [int(i)-1 for i in input().split()]
maze = [[i for i in input()] for j in range(H)]
dp = [[-1 for i in range(W)] for j in range(H)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp[C[0]][C[1]] = 0
pos = deque([[C[0], C[1], 0]])

while len(pos) > 0:

    h, w, count = pos.popleft()

    for dh, dw in dir:
        if h+dh<0 or H-1<h+dh or w+dw<0 or W-1<w+dw:
            continue
        elif maze[h+dh][w+dw] == "#":
            continue
        elif dp[h+dh][w+dw] == -1 or count < dp[h+dh][w+dw]:
            dp[h+dh][w+dw] = count
            pos.append([h+dh, w+dw, count])

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if h+dh<0 or H-1<h+dh or w+dw<0 or W-1<w+dw:
                continue
            elif maze[h+dh][w+dw] == "#":
                continue
            elif dp[h+dh][w+dw] == -1 or count + 1 < dp[h+dh][w+dw]:
                dp[h+dh][w+dw] = count + 1
                pos.append([h+dh, w+dw, count+1])

print(dp[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Dijkstra
def Dijkstra(D,From,To,with_path=False):
    """Dijksta法を用いて,FromからToまでの距離を求める.

    D:辺の重みが全て非負の有向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

    (出力の結果)
    with_path=True->(距離,最短経路の辿る際の前の頂点)
    with_path=False->距離
    """
    from copy import copy
    from heapq import heappush,heappop

    T={v:float("inf") for v in D.vertex}
    T[From]=0

    if with_path:
        Prev={v:None for v in D.vertex}

    Q=[(0,From)]

    Flag=False
    while Q:
        c,u=heappop(Q)

        if u==To:
            Flag=True
            break

        if T[u]<c:
            continue

        for v in D.adjacent_out[u]:
            if T[v]>T[u]+D.adjacent_out[u][v]:
                T[v]=T[u]+D.adjacent_out[u][v]
                heappush(Q,(T[v],v))

                if with_path:
                    Prev[v]=u

    if not Flag:
        if with_path:
            return (float("inf"),None)
        else:
            return float("inf")

    if with_path:
        path=[To]
        u=To
        while (Prev[u]!=None):
            u=Prev[u]
            path.append(u)
        return (T[To],path[::-1])
    else:
        return T[To]
#=====================================
def No_to_Pos(N):
    return (N//W+1,N%W+1)

def Pos_to_No(x,y):
    return (x-1)*W+(y-1)

def dist(P,Q):
    return max(abs(P[0]-Q[0]),abs(P[1]-Q[1]))
#=====================================
H,W=map(int,input().split())
FROM=tuple(map(int,input().split()))
TO=tuple(map(int,input().split()))

S=["*"*(W+2)]
for x in range(H):
    S+=["*"+input()+"*"]
S+=["*"*(W+2)]

U=Union_Find(H*W)

for a in range(1,H+1):
    for b in range(1,W+1):
        if S[a][b]==S[a+1][b]==".":
            U.union(Pos_to_No(a,b),Pos_to_No(a+1,b))
        if S[a][b]==S[a][b+1]==".":
            U.union(Pos_to_No(a,b),Pos_to_No(a,b+1))


P=set()
for u in U.roots():
    x,y=No_to_Pos(u)
    if S[x][y]==".":
        P.add(u)
P=list(P)
D=Digraph(P)
K=list(D.vertex)

for i in range(D.vertex_number):
    for j in range(i+1,D.vertex_number):
        for P in U.members(K[i]):
            for Q in U.members(K[j]):
                if dist(No_to_Pos(P),No_to_Pos(Q))<=2:
                    D.add_edge(K[i],K[j],1)
                    D.add_edge(K[j],K[i],1)

T=Dijkstra(D,U.find(Pos_to_No(*FROM)),U.find(Pos_to_No(*TO)))

if T==float("Inf"):
    print(-1)
else:
    print(T)

assert 1

Submission status: Time Limit Exceeded

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set != deque([]):
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve():
    from collections import deque
    import heapq

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

    que = []
    heapq.heapify(que)
    heapq.heappush(que, [0, Ch, Cw])  # [ワープ回数, h座標, w座標]
    visited = set()
    while len(que) != 0:
        n, y, x = heapq.heappop(que)
        visited.add((y, x))

        # ゴールか？
        if y == Dh and x == Dw:
            print(n)
            return

        # 上下左右移動可能ならばqueに入れる
        for ny, nx in ([y-1, x], [y+1, x], [y, x-1], [y, x+1]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n, ny, nx])
        # ワープ可能位置をqueに入れる
        for ny, nx in ([y-2, x-2], [y-2, x-1], [y-2, x], [y-2, x+1], [y-2, x+2],
                       [y-1, x-2], [y-1, x-1], [y-1, x+1], [y-1, x+2],
                       [y, x-2], [y, x+2],
                       [y+2, x-2], [y+2, x-1], [y+2, x], [y+2, x+1], [y+2, x+2],
                       [y+1, x-2], [y+1, x-1], [y+1, x+1], [y+1, x+2]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n+1, ny, nx])

    # ゴールはたどり着かなかったよ・・・
    print(-1)
    return


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e10

class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    
    

def dijkstra(adj, sx, sy):
    Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
    D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, ux, uy = PQ.pop() # 最小コストなノードu

        Color[ux][uy] = 1 # uをVisitedに。

        if D[ux][uy] < min_cost:
            # 更新の必要なし.
            continue

        for adj_x, adj_y, adj_w in adj[(ux, uy)]:
            if not Color[adj_x][adj_y]: #訪問済みでないなら
                if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                    D[adj_x][adj_y] = D[ux][uy] + adj_w
                    # P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                    
    
    return D


H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [["#"]*(W+2) for _ in range(H+2)]
for i in range(1,1+H):
    tmp=list(input())
    for j in range(1,1+W):
        S[i][j]=tmp[j-1]

idxs = []

for row in range(1, H+1):
    for col in range(1, W+1):
        if S[row][col] == ".":
            idxs.append((row, col))

dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
graph = {idx: deque() for idx in idxs}
for x in range(1, H+1):
    for y in range(1, W+1):
        if S[x][y] == "#":
            continue
        idxs.append((x, y))
        for dx, dy in dxdy:
            if S[x+dx][y+dy] == ".":
                graph[(x, y)].append((x+dx, y+dy, 0))
                

for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if x+dx < 1 or x+dx>H or y+dy<1 or y+dy>W:
                continue
            if S[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy, 1))

D = dijkstra(graph, ch, cw)
if D[dh][dw] == INF:
    print(-1)
else:
    print(D[dh][dw])