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 deque
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q_walk = deque()
    q_warp = deque()
    q_walk.append((x, y))
    while len(q_walk) > 0:
        x, y = q_walk.popleft() 
        q_warp.append((x, y))
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q_walk.append((nx, ny))
        if len(q_walk) == 0:
            while len(q_warp) > 0:
                x2, y2 = q_warp.popleft()
                for dxx in range(-2, 3):
                    for dyy in range(-2, 3):
                        nxx = x2 + dxx
                        nyy = y2 + dyy 
                        if not 0 <= nxx < h or not 0 <= nyy < w:
                            continue
                        if maze[nxx][nyy] == "#":
                            continue
                        if dist[nxx][nyy] <= d+1:
                            continue
                        dist[nxx][nyy] = d+1
                        q_walk.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])

Submission status: Time Limit Exceeded

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

from collections import deque

q = 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 = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
cost_list = [[INF for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

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

from collections import deque

q = 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 = 10 ** 18
org_list = [INF for i in range(h)]
cost_list = [[INF for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  org_list[i] = s


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  # print("-------------")
  # loopc -= 1

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  # print(ph, pw, cost)

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      # print("４ついか")
      q.appendleft([nh, nw])



  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        # print("jついか")
        q.append([ph + i, pw + j])


  # 最後デバッグ
  # for li in org_list:
  # #   print(li)
  # for li in cost_list:
  #   print(li)

  # print(q)

  # loop = False

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft() 
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q.appendleft((nx, ny))

        for dxx in range(-2, 3):
            for dyy in range(-2, 3):
                 nxx = x + dxx
                 nyy = y + dyy 
                 if not 0 <= nxx < h or not 0 <= nyy < w:
                    continue
                 if maze[nxx][nyy] == "#":
                    continue
                 if dist[nxx][nyy] <= d+1:
                    continue
                 dist[nxx][nyy] = d+1
                 q.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])

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())
S = []
for _ in range(H):
    s = input()
    S.append(s)

# 上下左右に移動できるところは移動する
# 移動してもたどり着けない場合はワープをそれぞれのますで実行し、まだ到達していない箇所にいく
# これを繰り返す

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

wx = [-2, -1, 0, 1, 2]
wy = [-2, -1, 0, 1, 2]
dp = [[-1] * W for _ in range(H)]
dp[Ch - 1][Cw - 1] = 0


def bfs(x, y, cost, dp, d):
    while len(d) > 0:
        p = d.popleft()
        for i in range(4):
            if p[0] + dx[i] >= 0 and p[0] + dx[i] < W and p[1] + \
                    dy[i] >= 0 and p[1] + dy[i] < H:
                if S[p[1] + dy[i]][p[0] + dx[i]
                                   ] == '.' and dp[p[1] + dy[i]][p[0] + dx[i]] == -1:
                    d.append([p[0] + dx[i], p[1] + dy[i]])
                    dp[p[1] + dy[i]][p[0] + dx[i]] = cost

    return cost, dp


dw = deque()
ds = deque()
ds.append([Cw - 1, Ch - 1])
c = 0
while True:
    cost, dp = bfs(Cw - 1, Ch - 1, c, dp, ds)
    for i in range(H):
        for j in range(W):
            if dp[i][j] == cost:
                dw.append([j, i])
    check = False
    while len(dw) > 0:
        p = dw.popleft()
        for m in range(5):
            for n in range(5):
                if p[0] + wx[m] >= 0 and p[0] + wx[m] < W and p[1] + \
                        wy[n] >= 0 and p[1] + wy[n] < H:
                    if S[p[1] + wy[n]][p[0] + wx[m]
                                       ] == '.' and dp[p[1] + wy[n]][p[0] + wx[m]] == -1:
                        ds.append([p[0] + wx[m], p[1] + wy[n]])
                        dp[p[1] + wy[n]][p[0] + wx[m]] = cost + 1
                        check = True
    if check:
        c += 1
    else:
        break


print(dp[Dh - 1][Dw - 1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    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())
    S = [input() for _ in range(H)]

    dist = defaultdict(lambda: float("inf"))
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h, w] == float("inf") or dist[h, w] > d:
            dist[h, w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    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)]

    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h, w] < dist[nh, nw] :
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                if abs(ddh) + abs(ddw) <= 1:
                    continue
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh, nw] > dist[h, w] + 1:
                        dist[nh, nw] = dist[h, w] + 1
                        queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    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)]

    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h, w] < dist[nh, nw] :
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh, nw] > dist[h, w] + 1:
                        dist[nh, nw] = dist[h, w] + 1
                        queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from collections import deque

q = 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

ban_list = [[-999 for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]


ban_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

while q:
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = ban_list[nh][nw]
    if val == "#" or val == cost:
      continue
    if val == "." or cost < val:
      ban_list[nh][nw] = cost
      q.appendleft([nh, nw])



  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])


result = ban_list[dh][dw]
if result == ".":
  result = -1


print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if (h, w) == (Dh, Dw):
            break

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh, nw] == float("inf") or dist[nh, nw] > d:
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw, d))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh, nw] == float("inf"):
                        if dist[nh, nw] > dist[h, w] + 1:
                            dist[nh, nw] = dist[h, w] + 1
                            queue.append((nh, nw, d + 1))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        if (h, w) == (Dh, Dw):
            break

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh, nw] == float("inf") or dist[nh, nw] > dist[h, w]:
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh, nw] == float("inf"):
                        if dist[nh, nw] > dist[h, w] + 1:
                            dist[nh, nw] = dist[h, w] + 1
                            queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w]
        elif dst[h][w] < dst[nh][nw]:
            dst[nh][nw] =  dst[h][w]
        else: continue
        dq.append((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)

now = [s]
ans = 0

def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])

while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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=1<<18

from numba import njit, b1, i4, i8, f8
# @njit((i8,i8,i8), cache=True)
@njit(cache=True)
def pos(W,h,w):
    return h * W + w

# @njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
@njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

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

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(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
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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=1<<18

from numba import njit, i1, i4, i8, f8
# @njit((i8,i8), cache=True)
@njit(cache=True)
def pos(h,w):
    return h * W + w

# @njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
@njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

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

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(*x)] < d: continue

        h,w = x
        normal = set([(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
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(*e)]:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(*e)] > dist[pos(*x)] + cost:
                    dist[pos(*e)] = dist[pos(*x)] + cost
                    heapq.heappush(hq,(dist[pos(*e)],e))

    # print(dist)
    if dist[pos(*t)] == INF: 
        dist[pos(*t)] = -1
        
    return dist[pos(*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,G)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def zero_origin(s: str) -> int:
  return int(s) - 1

h, w = map(int, input().split())
ch, cw = map(zero_origin, input().split())
dh, dw = map(zero_origin, input().split())
s = [input() for _ in range(h)]
active = [
  [True if s[i][j] == '.' else False for j in range(w)]
  for i in range(h)]

magic = 0
stack = [(ch, cw)]
active[ch][cw] = False
visited = []
while stack:
  cur_i, cur_j = stack.pop()
  visited.append((cur_i, cur_j))
  for di, dj in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
    i = cur_i + di
    j = cur_j + dj
    if 0 <= i < h and 0 <= j < w and active[i][j]:
      stack.append((i, j))
      active[i][j] = False
  if not active[dh][dw]:
    print(magic)
    break
  if not stack:
    magic += 1
    while visited:
      cur_i, cur_j = visited.pop()
      for i in range(cur_i - 2, cur_i + 3):
        for j in range(cur_j - 2, cur_j + 3):
          if 0 <= i < h and 0 <= j < w and active[i][j]:
            stack.append((i, j))
            active[i][j] = False
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
            dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])

Submission status: Time Limit Exceeded

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = min(dst[nh][nw], dst[h][w] + 1)
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
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)

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

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

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

    dist = defaultdict(lambda: INF) # sからxでの最短距離
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue
        
        h,w = x
        normal = set([(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
                e = (new_h,new_w)
                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 e in normal:
                    cost -= 1
                
                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()