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, defaultdict
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    # G = [set() for _ in range(area_num_count)]

    # for h in range(H):
    #     for w in range(W):
    #         from_area_num = S[h][w]
    #         if from_area_num == '#':
    #             continue
    #         from_area_num = int(from_area_num)

    #         for dh in range(2+1):
    #             if h+dh < 0 or h+dh >= H:
    #                 continue
    #             for dw in range(-2,2+1):
    #                 if w+dw < 0 or w+dw >= W:
    #                     continue
    #                 to_area_num = S[h+dh][w+dw]
    #                 if to_area_num == '#':
    #                     continue
    #                 to_area_num = int(to_area_num)
    #                 if from_area_num != to_area_num:
    #                     G[to_area_num].add(from_area_num)
    #                     G[from_area_num].add(to_area_num)

    # G = [[] for _ in range(area_num_count)]
    G = defaultdict(set)
    used = [set() for _ in range(area_num_count)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if S[h+dh][w+dw] == "#":
                        continue
                    if S[h][w] == S[h+dh][w+dw]:
                        continue
                    if S[h+dh][w+dw] in used[int(S[h][w])]:
                        continue
                    G[int(S[h][w])].add((int(S[h+dh][w+dw])))
                    used[int(S[h][w])].add((S[h+dh][w+dw]))
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys
import numpy as np

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 


MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = np.full((H, W), 10**9, dtype=np.int64)

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que.popleft()

    if dist[h][w] <= cost:
        continue

    dist[h][w] = cost

    if h == DH and w == DW:
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    warpcost = cost + 1
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh == 0 and dw == 0:
                continue
            nh = h + dh 
            nw = w + dw 
            if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
                que.append((nh, nw, warpcost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 10 ** 9
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2

move_list = []
for i in range(5):
  for j in range(5):
    if (i, j) == (2, 2):
      continue
    elif (i, j) == (1, 2) or (i, j) == (2, 1) or (i, j) == (2, 3) or (i, j) == (3, 2):
      move_list.append((0, i-2 + W*(j-2)))
    else:
      move_list.append((1, i-2 + W*(j-2)))

def dijkstra(s):
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [float("inf")] * (H*W)
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for dc, dv in move_list:
      w = v + dv
      tmp = cost[v] + dc
      if grid[w] == "#":
        continue
      if tmp < cost[w]:
        cost[w] = tmp
        heapq.heappush(hq, (tmp, w))
  return cost

ans = dijkstra( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 


MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que.popleft()

    if dist[h][w] <= cost:
        continue

    dist[h][w] = cost

    if h == DH and w == DW:
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    warpcost = cost + 1
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh == 0 and dw == 0:
                continue
            nh = h + dh 
            nw = w + dw 
            if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
                que.append((nh, nw, warpcost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    G = [set() for _ in range(area_num_count)]

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2

magic_list = []
for i in range(5):
  for j in range(5):
    if (i, j) in [(2, 2), (1, 2), (2, 1), (2, 3), (3, 2)]:
      continue
    else:
      magic_list.append(i-2 + W*(j-2))

move_list = [-1, 1, W, -W]

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * (H*W)
  dist[start] = 0
  q = deque([start])
  while q:
    v = q.popleft()
    dv = dist[v]
    for move in move_list:
      w = v + move
      if grid[w] == '#':
        continue
      dw = dv
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.appendleft(w)
    for magic in magic_list:
      w = v + magic
      if grid[w] == '#':
        continue
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
  return dist

ans = bfs( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == 10**9:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    # G = defaultdict(set)
    G = [set() for _ in range(area_num_count)]

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        # G[to_area_num].add(from_area_num)
                        # G[from_area_num].add(to_area_num)
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch,cw,dh,dw=ch-1,cw-1,dh-1,dw-1
S=[data() for i in range(h)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
dist=[[INF]*w for i in range(h)]
dist[ch][cw]=0

queue = [(0, ch, cw)]
while queue:
    path_len, u, v = heappop(queue)
    if path_len == dist[u][v]:
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= u + i < h and 0 <= v + j < w and S[u + i][v + j] == '.':
                    if (i,j) in steps:
                        if path_len < dist[u+i][v+j]:
                            dist[u+i][v+j] = path_len
                            heappush(queue, (path_len, u+i, v+j))
                    else:
                        if 1 + path_len < dist[u + i][v + j]:
                            dist[u + i][v + j] = 1 + path_len
                            heappush(queue, (1 + path_len, u + i, v + j))


if dist[dh][dw]!=INF:
    out(dist[dh][dw])
else:
    out(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

from sys import stdin
readline = stdin.readline

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
for h in range(H):
    th = t[h]
    Sh = S[h]
    for w in range(W):
        if Sh[w] == '#':
            th[w] = -1

t[Ch][Cw] = 0
q = deque([(Ch, Cw)])
while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        ti = t[i]
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if ti[j] <= a + 1:
                continue
            ti[j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 

MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que[0]
    que.popleft()

    if dist[h][w] <= cost:
        continue

    dist[h][w] = cost

    if h == DH and w == DW:
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    warpcost = cost + 1
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh == 0 and dw == 0:
                continue
            nh = h + dh 
            nw = w + dw 
            if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
                que.append((nh, nw, warpcost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 2*H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    D = [[-1] * W for _ in [0] * H]  # -1がINFを意味する
    que = [(0, si, sj)]
    while que:
        c, i, j = heappop(que)
        if D[i][j] != -1:
            continue
        D[i][j] = c
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
                nc = c
            else:  # ワープして行ける
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from itertools import product, permutations, combinations

# もし歩くだけなら簡単
# ワープをどう処理する？
# もし周囲5*5を候補にするなら24*10**6 んー間に合うか微妙


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
D = grid_dijkstra(S, si, sj)
print(D[ti][tj] if D[ti][tj] != INF else -1)
# print(*D, sep='\n')

# unionfindで連結成分切り出してから、連結成分をまたぐときだけ+1するdfsかな?

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 = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 

MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que[0]
    que.popleft()

    if dist[h][w] <= cost:
        continue

    dist[h][w] = cost

    if (h, w) == (DH, DW):
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    warpcost = cost + 1
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            nh = h + dh 
            nw = w + dw 
            if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
                que.append((nh, nw, warpcost))

#for i in range(H):
#    print (MAZE[i])
print(ret)