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 defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

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

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = []
    heapq.heappush(hq,(0,s))

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d1 = deque()
d.append((Ch, Cw))
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2,-1,0,1,2]
while True:
  # 行けるところすべて追加
  targets = set()
  while len(d) > 0:
    temps = set(d)
    targets |= temps
    d = deque()
    for Th, Tw in temps:
      for i,j in a:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          s.add((Th,Tw))
  # クリアしてるか確認
  if (Dh,Dw) in targets:
    print(ans)
    exit()
  else:
    d = deque()
    ans += 1
    for Th,Tw in targets:
      for i in b:
        for j in b:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
            s.add((Th,Tw))
    if len(d) == 0:
      print('-1')
      exit()

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())
cost=[[-1 for i in range(W)] for j in range(H)]
queue = [[Ch-1, Cw-1] for j in range(1)]
queue2 = [[] for j in range(0)]
S=[[i,j] for j in range(0)]
cost[Ch-1][Cw-1]=0
costCount = 1
checkCount = 0
for i in range(H):
    S.append(list(input()))
while(cost[Dh-1][Dw-1]<0 and len(queue)>0):
    while(len(queue)>0):
        posX = queue[0][0]
        posY = queue[0][1]
        #print(posX,posY)
        queue2.append(queue.pop(0))
        if posX+1<H:
            if cost[posX+1][posY]<0 and S[posX+1][posY]==".":
                cost[posX+1][posY] = cost[posX][posY]
                queue.append([posX+1,posY])
        if posY+1<W:
            if cost[posX][posY+1]<0 and S[posX][posY+1]==".":
                cost[posX][posY+1] = cost[posX][posY]
                queue.append([posX,posY+1]) 
        if posX-1>=0:
            if cost[posX-1][posY]<0 and S[posX-1][posY]==".":
                cost[posX-1][posY] = cost[posX][posY]
                queue.append([posX-1,posY])
        if posY-1>=0:
            if cost[posX][posY-1]<0 and S[posX][posY-1]==".":
                cost[posX][posY-1] = cost[posX][posY]
                queue.append([posX,posY-1]) 
    #print(cost)
    for a in range(len(queue2)):
            i=queue2[a][0]
            j=queue2[a][1]
            if cost[i][j]>=0:
                for k in range(max(0,i-2), min(H,i+3)):
                    for l in range(max(0,j-2), min(W,j+3)):
                        if cost[k][l]<0 and S[k][l]==".":
                            cost[k][l] = costCount
                            queue.append([k,l])
    costCount+=1
#print(cost)
print(cost[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

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

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d1 = deque()
d.append((Ch, Cw))
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2,-1,0,1,2]
while True:
  # 行けるところすべて追加
  targets = set()
  while len(d) > 0:
    temps = set(d)
    targets |= temps
    d = deque()
    for Th, Tw in temps:
      for i,j in a:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          s.add((Th,Tw))
  # クリアしてるか確認
  if (Dh,Dw) in targets:
    print(ans)
    exit()
  else:
    s |= targets
    d = deque()
    for Th,Tw in targets:
      for i in b:
        for j in b:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = [[] for _ in range(mx)]

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())#行,列
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [list(input()) for _ in range(h)]

cost = {i:{j:-1 for j in range(w)} for i in range(h)}
cost[C[0]-1][C[1]-1]=0
cost_base = 0
for i,v in cost.items():
    for j in v.keys():
        if S[i][j]=='#':
            cost[i][j]=-2

ok = True

q=deque()
while cost[D[0]-1][D[1]-1]==-1:
    #スタート(初回)と、前回ループで移動Bで初めて行けたマスの登録
    for i,v in cost.items():
        for j,v_ in v.items():
            if v_==cost_base:
                q.append([i+1,j+1])
                
    #どちらの移動でも、ゴール踏破前に未踏破のマスに行けなかった場合
    if len(q)==0:
        ok = False
        break
                
    #移動Aで行けるマスを全探索
    while len(q)>0:
        now = q.popleft()
        for i in range(-1,2,2):
            if now[0]+i<1 or now[0]+i>h:
                continue
            if cost[now[0]+i-1][now[1]-1]==-1:
                cost[now[0]+i-1][now[1]-1]=cost_base
                q.append([now[0]+i,now[1]])
        for i in range(-1,2,2):
            if now[1]+i<1 or now[1]+i>w:
                continue
            if cost[now[0]-1][now[1]+i-1]==-1:
                cost[now[0]-1][now[1]+i-1]=cost_base
                q.append([now[0],now[1]+i])

    #移動Aで行けたマスから移動Bで行け、かつ今まで行けなかったマスの探索
    for _h,v in cost.items():
        for _w,v_ in v.items():
            if v_==cost_base:
                
                for i in range(-2,3):
                    for j in range(-2,3):
                        if _h+1+i<1 or _h+1+i>h:
                            continue
                        if _w+1+j<1 or _w+1+j>w:
                            continue

                        if cost[_h+i][_w+j]==-1:
                            cost[_h+i][_w+j]=cost_base+1
    cost_base+=1
    
    
if ok:
    print(cost[D[0]-1][D[1]-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
from numba import jit

sys.setrecursionlimit(10**8)

@jit
def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        if s[i,j]=='.': 
            q.append([i,j])
            s[i,j]=int(s[a,b])
        elif len(wq)==0 or ( len(wq)>0 and wq[-1]!=[a,b]  ):
            wq.append([a,b])

    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                edge[x].append((y,0))
                edge[y].append((x,0))
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,1))
                    edge[y].append((x,1))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        if s[i,j]=='.': 
            q.append([i,j])
            s[i,j]=int(s[a,b])
        elif len(wq)==0 or (len(wq)>0 and wq[-1]!=[a,b]):
            wq.append([a,b])

    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    cost = [[INF] * mx for _ in range(mx)]
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                cost[x][y] = 0
                cost[y][x] = 0
                edge[x].append(y)
                edge[y].append(x)
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    cost[x][y] = min(cost[x][y],1)
                    cost[y][x] = min(cost[y][x],1)
                    edge[x].append(y)
                    edge[y].append(x)
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e in edge[x]:
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        h, w, c = que.popleft()
        if c != 0:
            visited[h][w] = min(visited[h][w], c)
        for mh, mw in move: # 移動A: 歩いて移動
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == INF:
                visited[ch][cw] = c
                que.appendleft((ch, cw, c))
        for wh in range(-2, 3): # 移動B: ワープ魔法
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == INF:
                    que.append((ch, cw, c+1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#dijkstra
import heapq
class Dijkstra:
    INF = 10**18

    def __init__(self, N, Graph=[[-1]]):
        self.N = (N+1)
        self.dist = [self.INF] * (N+1)
        if Graph[0][0]!=-1: self.G = Graph
        else: self.G = [[] for _ in range(N+1)]

    def insert(self, From, To, Cost):
        self.G[From].append([To, Cost])

    def reset(self):
        for i in range(self.N): self.dist[i] = self.INF

    def dijkstra(self, st):
        self.reset()
        hq = [(0, st)]
        heapq.heapify(hq)
        while len(hq):
            tmp = heapq.heappop(hq)
            now, now_dist = tmp[1], tmp[0]
            if self.dist[now] <= now_dist: continue
            self.dist[now] = now_dist
            for to in self.G[now]:
                heapq.heappush(hq, (now_dist+to[1], to[0]))

#verify https://atcoder.jp/contests/abc164/submissions/12511253

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: 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())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [list(input()) for _ in range(h)]

def bfs(sy, sx):
    que = deque([])
    que.append([sy, sx])

    while que:
        y, x = que.popleft()
        dx, dy = [0,1,0,-1], [1,0,-1,0]
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if s[ny][nx] == '#': continue
            if seen[ny][nx] != -1: continue
            
            seen[ny][nx] = seen[y][x]
            que.append([ny, nx])
            wp.append([ny, nx])

            
dq = deque([])
dq.append([ch, cw])
seen = [[-1]*w for _ in range(h)]
seen[ch][cw] = 0
wp = deque([])
while dq:
    while dq:
        y, x = dq.popleft()
        wp.append([y, x])
        bfs(y, x)

    ok = False
    while wp:
        y, x = wp.popleft()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0: continue
                ny, nx = y+dy, x+dx
                if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
                if s[ny][nx] == '#': continue
                if seen[ny][nx] >= 0: continue

                ok = True
                seen[ny][nx] = seen[y][x] + 1
                dq.append([ny, nx])

    if not ok: break

if seen[dh][dw] >= 0:
    print(seen[dh][dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append([cost * self.threshold + Y, 0])

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, [st, 0])
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)[0]
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to[0] // self.threshold
                to_node = to[0] - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, [to_cost * self.threshold + to_node, 0])

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)