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
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = defaultdict(lambda : -1)
    costmap[Cw, Ch] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[nx, ny] == -1 or costmap[x, y] < costmap[nx, ny]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[nx, ny] = costmap[x, y]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[nx, ny] == -1 or costmap[x, y] < costmap[nx, ny]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[nx, ny] = costmap[x, y] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dw, Dh])

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

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())

start = tuple(map(lambda x:x - 1, map(int,input().split())))
goal = tuple(map(lambda x:x - 1, map(int,input().split())))

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

from collections import deque
q = deque([])

# 頂点, コスト
q.append([start[0], start[1], 0])
INF = 10 ** 10
cost = [[INF] * W for i in range(H)]

while q:
  y,x,c = q.popleft()
  if S[y][x] == "#":
    continue
  if cost[y][x] <= c:
    continue
  cost[y][x] = c
  for i in range(-2,3):
    for j in range(-2,3):
      if i == 0 and j == 0:
        continue
      if 0 <= y + i < H and 0 <= x + j < W:
        if abs(i) + abs(j) == 1:
          q.appendleft([y + i, x + j, c])
        else:
          q.append([y + i, x + j, c + 1])

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

Submission status: Time Limit Exceeded

Solution code:
#ABC176D

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]

stack = deque()
stack.append([ch-1,cw-1])
INF=10**10
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0] + dxdy]:
            warp += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict
import heapq as hp
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def is_valid(i, j):
        if 0 <= i < h and 0 <= j < w and ar[i][j] == 1:
            return True
        return False

    ar=[]
    for _ in range(h):
        ar.append([1 if i=="." else 0 for i in input() ])

    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    magic = [(0, 2), (2, 0), (0, -2), (-2, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (1, 2), (1, -2), (-1, 2), (-1, -2),
             (2, 1), (2, -1), (-2, 1), (-2, -1), (2, 2), (2, -2), (-2, 2), (-2, -2)]

    queue=[(0,ch-1,cw-1)]
    hp.heapify(queue)
    inf=float("inf")
    di=[[inf]*(w+1) for _ in range(h+1) ]
    di[ch-1][cw-1]=0
    while queue:
        d,a,b=hp.heappop(queue)
        ar[a][b]=0
        if a==dh-1 and b==dw-1:
            print(di[a][b])
            exit()
        for i in move:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[x][y]=min(di[x][y],d)
                hp.heappush(queue, (di[x][y], x, y))


        for i in magic:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[x][ y] = min(di[x][ y], d+1)
                hp.heappush(queue, (di[x][ y], x, y))

    if di[dh-1][dw-1]==float("inf"):
        print(-1)
    else:
        print(di[dh-1][dw-1])






solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict
import heapq as hp
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def is_valid(i, j):
        if 0 <= i < h and 0 <= j < w and ar[i][j] == 1:
            return True
        return False

    ar=[]
    for _ in range(h):
        ar.append([1 if i=="." else 0 for i in input() ])

    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    magic = [(0, 2), (2, 0), (0, -2), (-2, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (1, 2), (1, -2), (-1, 2), (-1, -2),
             (2, 1), (2, -1), (-2, 1), (-2, -1), (2, 2), (2, -2), (-2, 2), (-2, -2)]

    queue=[(0,ch-1,cw-1)]
    hp.heapify(queue)
    def g():
        return float("inf")
    di=defaultdict(g)
    di[(ch-1,cw-1)]=0
    while queue:
        d,a,b=hp.heappop(queue)
        ar[a][b]=0
        if a==dh-1 and b==dw-1:
            print(di[(a,b)])
            exit()
        for i in move:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[(x,y)]=min(di[(x,y)],d)
                hp.heappush(queue, (di[(x,y)], x, y))


        for i in magic:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[(x, y)] = min(di[(x, y)], d+1)
                hp.heappush(queue, (di[(x, y)], x, y))

    if di[(dh-1,dw-1)]==float("inf"):
        print(-1)
    else:
        print(di[(dh-1,dw-1)])






solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict
import heapq as hp
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def is_valid(i, j):
        if 0 <= i < h and 0 <= j < w and ar[i][j] == 1:
            return True
        return False

    ar=[]
    for _ in range(h):
        ar.append([1 if i=="." else 0 for i in input() ])

    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    magic = [(0, 2), (2, 0), (0, -2), (-2, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (1, 2), (1, -2), (-1, 2), (-1, -2),
             (2, 1), (2, -1), (-2, 1), (-2, -1), (2, 2), (2, -2), (-2, 2), (-2, -2)]

    queue=[(0,ch-1,cw-1)]
    hp.heapify(queue)
    def g():
        return float("inf")
    di=defaultdict(g)
    di[(ch-1,cw-1)]=0
    while queue:
        d,a,b=hp.heappop(queue)
        ar[a][b]=0
        for i in move:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[(x,y)]=min(di[(x,y)],d)
                hp.heappush(queue, (di[(x,y)], x, y))


        for i in magic:
            x,y=a+i[0],b+i[1]
            if is_valid(x,y):

                di[(x, y)] = min(di[(x, y)], d+1)
                hp.heappush(queue, (di[(x, y)], x, y))

    if di[(dh-1,dw-1)]==float("inf"):
        print(-1)
    else:
        print(di[(dh-1,dw-1)])






solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 10:54:09 2020

@author: Kozu
"""
from collections import deque
import numpy as np    

#標準入力
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H):    
  S.append(list(input()))
  
#定数
Wall = -1
WildArea = 1e9
#変数
T = np.full([H + 4,W + 4],Wall)
t = 0
Deque = deque()
#右上左下
dx = [1,0,-1,0]
dy = [0,1,0,-1]


#初期処理
for i in range(2):
    C[i] -= 1
    D[i] -= 1
    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i + 2][j + 2] = Wall
        if S[i][j] == '.':
            T[i + 2][j + 2] = WildArea


T[C[0] + 2][C[1] + 2] = 0
Deque.append([C[0] + 2,C[1] + 2])

while True:
    n = Deque.pop()
    
    t = T[n[0]][n[1]]
    
    #BFS 幅優先探索
    for i in range(4):
        if T[n[0] + dx[i]][n[1] + dy[i]] == Wall:
            continue
        if T[n[0] + dx[i]][n[1] + dy[i]] <= t:
            continue
        
        T[n[0] + dx[i]][n[1] + dy[i]] = t
        Deque.append([n[0] + dx[i],n[1] + dy[i]])
    
    #Warp　ワープ
    for i in range(-2,3):
        for j in range(-2,3):
            if T[n[0]+ i][n[1] + j] == Wall:
                continue
            if T[n[0]+ i][n[1] + j] <= t + 1:
                continue
            T[n[0]+ i][n[1] + j] = t + 1
            Deque.appendleft([n[0]+ i,n[1] + j])            

    if len(Deque) <= 0:
        break;

            
            
ans = T[D[0] + 2][D[1] + 2]
if ans == WildArea:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
ch,cw = na()
dh,dw = na()
ch,cw = ch-1,cw-1
dh,dw = dh-1,dw-1
s = []
for i in range(h):
  s.append(ns())

from collections import deque

g = [[10000000000]*w for i in range(h)]
g[ch][cw] = 0
d = deque([(ch,cw,0)])

while d:
  x,y,num = d.popleft()
  pq = [(-1,0),(0,1),(1,0),(0,-1)]
  for p,q in pq:
    if not (0<=x+p<h and 0<=y+q<w):
      continue
    u = s[x+p][y+q]
    if u == '.':
      if num < g[x+p][y+q]:
        g[x+p][y+q] = num
        d.append((x+p,y+q,num))

  for i in range(-2,3):
    for j in range(-2,3):
      if not (0<=x+i<h and 0<=y+j<w):
        continue
      p = s[x+i][y+j]
      if p == '.':
        if num+1 < g[x+i][y+j]:
          g[x+i][y+j] = num+1
          d.append((x+i,y+j,num+1))

ans = g[dh][dw]

print('-1' if ans == 10000000000 else ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    que = [(0, DH, DW)]
    cnt[DH][DW] = 0
    while len(que) > 0:
        c, h, w = heapq.heappop(que)
        for dh, dw in [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
            [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
            [0, -2], [0, -1], [0, 1], [0, 2], \
            [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
            [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]:
            nh, nw = h + dh, w + dw
            if not (0 <= nh < H) or not (0 <= nw < W) or S[nh][nw] == '#':
                continue
            nc = c + 1
            if [dh, dw] in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nc = c
            if cnt[nh][nw] > nc:
                cnt[nh][nw] = nc
                heapq.heappush(que, (nc, nh, nw))

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import heapq


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    que = [(0, DH, DW)]
    cnt[DH][DW] = 0
    while len(que) > 0:
        c, h, w = heapq.heappop(que)
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if dh == dw == 0 or not (0 <= nh < H) or \
                not (0 <= nw < W) or S[nh][nw] == '#':
                continue
            nc = c
            if [dh, dw] not in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nc += 1
            if cnt[nh][nw] > nc:
                cnt[nh][nw] = nc
                heapq.heappush(que, (nc, nh, nw))

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys


sys.setrecursionlimit(10**7)


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    def dfs(h=DH, w=DW, c=0):
        if c >= cnt[h][w]:
            return
        cnt[h][w] = c
        # 上下左右なら回数据え置き
        for dh, dw in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                dfs(nh, nw, c)
        # それ以外はワープ
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            if [dh, dw] in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                continue
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                 dfs(nh, nw, c + 1)

    dfs()
    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys


sys.setrecursionlimit(10**7)


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    def dfs(h=DH, w=DW, c=0):
        if c >= cnt[h][w]:
            return
        cnt[h][w] = c
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                # 上下左右なら回数据え置き
                if [dh, dw] in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                    dfs(nh, nw, c)
                # それ以外はワープ
                else:
                    dfs(nh, nw, c + 1)

    dfs()
    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

def input():
    return sys.stdin.readline()[:-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] <= reached[h][w]:
                continue
            reached[nh][nw] = reached[h][w]
            heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] <= reached[h][w] + cost:
                    continue
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] <= reached[h][w]:
                continue
            reached[nh][nw] = reached[h][w]
            heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] <= reached[h][w] + cost:
                    continue
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
            reached[nh][nw] = d
            l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
                reached[nh][nw] = d + 1
                l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools


def resolve(in_):
    H, W = map(int, next(in_).split())
    Ch, Cw = map(int, next(in_).split())
    Dh, Dw = map(int, next(in_).split())

    ch = Ch - 1
    cw = Cw - 1
    dh = Dh - 1
    dw = Dw - 1
    S = tuple(s.strip() for s in in_)
    wall_i = ord(b'#')
    # road_i = ord(b'.')
    used = [[False for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append((ch, cw))
    for ans in itertools.count():
        if not qu:
            return -1
        
        roads = []
        # walk
        while qu:
            h, w = qu.popleft()
            if used[h][w]:
                continue
            
            used[h][w] = True
            roads.append((h, w))
            if dh == h and dw == w:
                return ans

            for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
                if not (0 <= h0 < H and 0 <= w0 < W):
                    continue
                if S[h0][w0] == wall_i:
                    continue
                qu.append((h0, w0))
        # magic
        for h1, w1 in roads:
            for h2 in range(h1 - 2, h1 + 3):
                for w2 in range(w1 - 2, w1 + 3):
                    if not (0 <= h2 < H and 0 <= w2 < W):
                        continue
                    if used[h2][w2]:
                        continue
                    if S[h2][w2] == wall_i:
                        continue
                    qu.append((h2, w2))

    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

h, w = list(map(int, input().split()))
c_h, c_w = list(map(int, input().split()))
d_h, d_w = list(map(int, input().split()))

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

adj = [[{} for _ in range(w)] for _ in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y] == ".":
            for i in [-2, -1, 0, 1, 2]:
                for j in [-2, -1, 0, 1, 2]:
                    if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == ".":
                        if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                            adj[x][y][(x+i, y+j)] = 0
                        elif i != 0 or j != 0:
                            adj[x][y][(x+i, y+j)] = 1

d = []

for x in range(h):
    for y in range(w):
        if x == c_h - 1 and y == c_w - 1:
            d.append([0, x, y])
        else:
            d.append([1000000, x, y])

heapq.heapify(d)

dist = [[1000000] * w for _ in range(h)]
dist[c_h-1][c_w-1] = 0

while len(d) > 0:
    e, x, y = heapq.heappop(d)
    if x == d_h-1 and y == d_w-1:
        break
    for k, v in adj[x][y].items():
        i, j = k
        if s[i][j] == "." and dist[i][j] > dist[x][y] + adj[x][y][(i, j)]:
            dist[i][j] = dist[x][y] + adj[x][y][(i, j)]
            heapq.heappush(d, [dist[i][j], i, j])

if dist[d_h-1][d_w-1] == 1000000:
    print(-1)
else:
    print(dist[d_h-1][d_w-1])

#print(adj)
#print(dist)