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 sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

ys,xs = (x-1 for x in readints())
yg,xg = (x-1 for x in readints())

maze = [readstr() for i in range(h)]

dist = [[10**10]*w for i in range(h)]

dq = deque()
dq.append([ys,xs])
dist[ys][xs] = 0

while dq:
    y,x = dq.popleft()
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.' and dist[y+dy][x+dx]>dist[y][x]:
                if abs(dy)+abs(dx)==1:
                    dq.appendleft((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x]
                else:
                    dq.append((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x] + 1

print(-1 if dist[yg][xg]==10**10 else dist[yg][xg])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque


# In[26]:


H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))


# In[27]:


ans = [[-1]*(W+4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2
ch += 1; cw += 1
dh += 1; dw += 1
ans[ch][cw] = 0


# In[28]:


move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [
    [-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]
    ]


# In[29]:


mylist = deque([[ch,cw]])
mylist2 = deque([])
while len(mylist) > 0:
    x,y = mylist.popleft()
    mylist2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            mylist.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(mylist) == 0:
        while len(mylist2) > 0:
            x2,y2 = mylist2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    mylist.append([i,j])
print(ans[dh][dw])


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    y, x, s = q.popleft()
    for dy, dx in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.' and path[ny][nx] > s:
            path[ny][nx] = s
            q.appendleft((ny, nx, s))
    for dy, dx in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
            path[ny][nx] = s + 1
            q.appendleft((ny, nx, s + 1))

ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque 
INF = float('INF') #INFの宣言
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
mymap = []
for h in range(H):
    mymap += [list(input())]


d = [ [INF for w in range(W)] for h in range(H) ] #各地点までの最短距離の配列,INFで初期化
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  #移動4方向のベクトル

def bfs(h, w, res):
    #warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = res            #スタート地点の距離を0にする
    # dequeが空になるまでループ
    while mydeque:
        #dequeの先頭を取り出す
        y, x = mydeque.popleft()
        #取り出してきた状態がGoalなら探索をやめる
        if y == Dh and x == Dw:
            print(res)
            sys.exit()
            break
        #移動4方向をループ
        for i in range(4):
            #移動後の点を(nx, ny) とする
            nx, ny = x + dx[i], y + dy[i]
            #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
            if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] ==  INF:
                #print(ny, nx, d[ny][nx], mymap[ny][nx])
                if  mymap[ny][nx] != '#' : 
                #移動できるならdequeに入れ、その点の距離を(x,y)からの距離+1で確定する
                    mydeque.append([ny, nx])
                    d[ny][nx] = res
    return #d[Dh][Dw]

def warp(h,w,res):
    if res%2 == 0:
        tgt_deque = main_deque2
    else:
        tgt_deque = main_deque1
    for i in range(-2,3):
        for j in range(-2,3):
            nx, ny = w + j, h + i
            if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] ==  INF:
                if  mymap[ny][nx] != '#' :
                    d[ny][nx] = res + 1
                    tgt_deque.append([ny, nx])
                    if ny == Dh and nx == Dw:
                         print(res+1)
                         sys.exit()
    return

turn = 0
main_deque1 = deque()
main_deque2 = deque()
main_deque1.append([Ch, Cw])
tgt_deque = main_deque1
#start地点からのbfs
while tgt_deque:
    #print(tgt_deque)
    h, w = tgt_deque.popleft()
    bfs(h,w,turn)
    for h in range(H):
        for w in range(W):
            if d[h][w] == turn:
                warp(h,w, turn)
    turn += 1
    if tgt_deque == main_deque1:
        tgt_deque = main_deque2
    else:
        tgt_deque = main_deque1
if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Ch][Cw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.appendleft((nx, ny, s + 1))

ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = []
for i in range(h):
  s.append(input())
cango = {}
d = {}
for i in range(h*w):
  d[i] = float('inf')
d[ch*w+cw] = 0
que = [ch*w+cw]
while que:
  v = que.pop(0)
  if v == dh*w+dw:
    break
  x, y = v % w, v // w
  if s[y][x] == "#":
    continue
  for i in range(max(0, x-2), min(w, x+3)):
    for j in range(max(0, y-2), min(h, y+3)):
      if s[j][i] == "#":
        continue
      if x == i and y == j:
        continue
      que.append(j*w+i)
      if abs(x-i) + abs(y-j) == 1:
        d[j*w+i] = min(d[v], d[j*w+i])
      else:
        d[j*w+i] = min(d[v]+1, d[j*w+i])
if d[dh*w+dw] == float('inf'):
  print(-1)
else:
  print(d[dh*w+dw])

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
maze = [list(input()) for i in range(H)]
#print(maze)
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[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]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

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
maze = [list(input()) for i in range(H)]
#print(maze)
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[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]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
ch-=1; cw-=1; dh-=1; dw-=1

def valid(i, j):
    if 0<=i<=h-1 and 0<=j<=w-1:
        return True
    else:
        return False

def bfs():
    que=[]
    m[ch][cw]=str(0)
    que.append((ch,cw))
    
    while que!=[]:
        i, j=que.pop(0)
        for si in range(-2, 3):
            for sj in range(-2, 3):
                f=False
                if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
                    if (si, sj)==(0,0):
                        pass
                    elif (si, sj)==(-1, 0) or (si, sj)==(0, -1) or (si, sj)==(1, 0) or (si, sj)==(0, 1):
                        if m[i+si][j+sj]=='.':
                            m[i+si][j+sj]=m[i][j]
                            f=True
                        else:
                            if int(m[i+si][j+sj])>int(m[i][j]):
                                m[i+si][j+sj]=m[i][j]
                                f=True
                    else:
                        if m[i+si][j+sj]=='.':
                            m[i+si][j+sj]=str(int(m[i][j])+1)
                            f=True
                        else:
                            if int(m[i+si][j+sj])>int(m[i][j])+1:
                                m[i+si][j+sj]=str(int(m[i][j])+1)
                                f=True
                if f:
                    que.append((i+si, j+sj))

bfs()

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    l1=list(range(w))
    l2=list(range(-2,3))
    for i in range(h):
        for j in l1:
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in l2:
                for dy in l2:
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in {(-1,0),(0,-1),(1,0),(0,1)}:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.

ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self.width * (h + 2) + w + 2

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

        unsearched = -1
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

            for dx in warp:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal]

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

h,w = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
link = defaultdict(list)
chg=10**4

for y in range(h):
    for x in range(w):
        if l[y][x]=="#":
            continue
        frm = y*chg+x
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                to=ny*chg+nx
                link[frm].append([to,0])

        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue
                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                    to=ny*chg+nx
                    link[frm].append([to,1])
def dks(g,start):
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

start = (sy-1)*chg+sx-1
goal = (gy-1)*chg+gx-1
ret=dks(link, start)
if goal in ret:
    print(ret[goal])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [0] * H
for i in range(H):
  maze[i] = str(input())
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i in [-2, -1, 0, 1, 2]:
    for j in [-2, -1, 0, 1, 2]:
      if (0 <= h + i < H) and (0 <= w + j < W):
        if i== 0 and j == 0:
          continue
        elif abs(i) + abs(j) == 1:
          if maze[h + i][w + j] == ".":
            if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
              ans[h + i][w + j] = cnt
              q.appendleft([cnt, h + i, w + j])
        else:
          if maze[h + i][w + j] == ".":
            if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
              ans[h + i][w + j] = cnt + 1
              q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in {(-1,0),(0,-1),(1,0),(0,1)}:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
link = defaultdict(list)
chg=10**4

for y in range(h):
    for x in range(w):
        if l[y][x]=="#":
            continue
        frm = y*chg+x
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                to=ny*chg+nx
                link[frm].append([to,0])

        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue
                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                    to=ny*chg+nx
                    link[frm].append([to,1])

def dks(g,start):
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

start = (sy-1)*chg+sx-1
goal = (gy-1)*chg+gx-1
ret=dks(link, start)
if goal in ret:
    print(ret[goal])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
path = [[10**10]*w for i in range(h)]
maze = []
for _ in range(h):
  s = input()
  maze.append(s)

walk = [(0,1),(1,0),(-1,0),(0,-1)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
Q = deque()
path[ch-1][cw-1]=0
Q.append((ch-1,cw-1,0))
while Q:
  hi,wi,c = Q.popleft()
  for i,j in walk:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]>c:
      path[nh][nw] = c
      Q.append((nh,nw,c))
  for i,j in warp:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]>c+1:
      path[nh][nw] = c+1
      Q.append((nh,nw,c+1))
print(path[dh-1][dw-1] if path[dh-1][dw-1]<10**10 else -1)