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: Runtime Error

Solution code:
from queue import deque
import heapq

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**20

ch -= 1
cw -= 1
dh -= 1
dw -= 1

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
bomb_count = 0

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]

    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        #elif lin[nx][ny] == inf:
        else:
            if lin[nx][ny] > lin[x][y]:
                se.add((nx,ny))
                lin[nx][ny] =lin[x][y]# 直接行ける
        
    # 魔法の力をもってすれば行ける
    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        else:
            if lin[nx][ny] > lin[x][y]+1:
                se.add((nx,ny))
                lin[nx][ny] = lin[x][y]+1

    que += se

if lin[dh][dw] == inf:
    print(-1)
else:
    print(lin[dh][dw])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop


class DisjointSet:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def dijkstra(adj_list, start):
    dist = defaultdict(lambda: float("inf"))
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))
    visited = set()
    while pq:
        w, v = heappop(pq)
        if dist[v] < w:
            continue
        visited.add(v)
        for nv, nw in adj_list[v]:
            if nv in visited:
                continue
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq, (dist[nv], nv))
    return dist


def solve():
    H, W = map(int, input().split())
    C_h, C_w = map(lambda x: int(x) - 1, input().split())
    D_h, D_w = map(lambda x: int(x) - 1, input().split())
    field = [list(input()) for _ in range(H)]

    ds = DisjointSet(H * W)
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                continue
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni = i + di
                nj = j + dj
                if 0 <= ni < H and 0 <= nj < W and field[ni][nj] != "#":
                    ds.union(j + i * H, nj + ni * H)

    g = defaultdict(set)
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                continue
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if di == 0 and dj == 0:
                        continue
                        ni = i + di
                        nj = j + dj
                    if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] != "#"):
                        continue
                    if ds.same(j + i * H, nj + ni * H):
                        g[(i, j)].add(((ni, nj), 0))
                        g[(ni, nj)].add(((i, j), 0))
                    else:
                        g[(i, j)].add(((ni, nj), 1))
                        g[(ni, nj)].add(((i, j), 1))

    dist = dijkstra(g, (C_h, C_w))
    ans = dist[(D_h, D_w)]
    print(-1) if ans == float("inf") else print(ans)


solve()

Submission status: Runtime Error

Solution code:
from collections import deque
R,C = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
c = [input() for i in range(R)]
visited = [[-1]*C for _ in range(R)]
warp = [[0]*C for _ in range(R)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()

  if [y,x] == [gy,gx]:
    print(warp[y][x])
    exit()
  for i,j in [(0,1),(1,0),(-1,0),(0,-1)]:
    if y+i >= R or y+i < 0 or x+j >= C or x+j < 0:
      continue
    if c[y+i][x+j] == '.' and visited[y+i][x+j] == -1:
      visited[y+i][x+j] = visited[y][x]+1
      warp[y+i][x+j] = warp[y][x]
      Q.append([y+i,x+j])
    elif c[y+i][x+j] == '#':
      for k,l in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,1),(1,-1),(-1,1)]:
        if y+i+k >= R or y+i+k < 0 or x+j+l >= C or x+j+l < 0:
          continue
        if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1:
          warp[y+i+k][x+j+l] = warp[y][x]+1
          visited[y+i+k][x+j+l] = visited[y+i][x+i]+1
          Q.append([y+i+k,x+j+l])
print(-1)

Submission status: Runtime Error

Solution code:
from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = [(W+4)*["#"]]+[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+[(W+4)*["#"]]+[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = []
Q = deque([[CH+1,CW+1]])
ans = 0

for n in range(1000):
  while Q:
    y,x = Q.popleft()
    P+=[[y,x]]
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q+=[[y+dy,x+dx]]

  if S[DH+1][DW+1]==".":
    for x,y in P:
      for dy,dx in [[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]]:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans+1
          Q+=[[y+dy,x+dx]]
    ans+=1

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


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


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)
G = nx.Graph()
path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    # path[h*W + w].append((0, new_h*W + new_w))
                    # path[new_h*W + new_w].append((0, h*W + w))
                    G.add_edge(h*W + w, new_h*W + new_w, weight=0)
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        # path[h*W + w].append((1, new_h*W + new_w))
                        # path[new_h*W + new_w].append((1, h*W + w))
                        G.add_edge(h*W + w, new_h*W + new_w, weight=1)
                for dy, dx in MAGIC:
                    new_h = h + dy
                    new_w = w + dx
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):
                        # path[h*W + w].append((1, new_h*W + new_w))
                        # path[new_h*W + new_w].append((1, h*W + w))
                        G.add_edge(h*W + w, new_h*W + new_w, weight=1)

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
# dist = dijkstra(path, N, c_h * W + c_w)
length = nx.dijkstra_path_length(G, c_h * W + c_w, d_h*W+d_w)
print(length)

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""

Submission status: Runtime Error

Solution code:
def f(i, j, wc):
    warp[i][j] = wc
    if i-1 >= 0 and s[i-1][j] == '.' and wc < warp[i-1][j]:
        f(i-1, j, wc)
    if j-1 >= 0 and s[i][j-1] == '.' and wc < warp[i][j-1]:
        f(i, j-1, wc)
    if i+1 < h and s[i+1][j] == '.' and wc < warp[i+1][j]:
        f(i+1, j, wc)
    if j+1 < w and s[i][j+1] == '.' and wc < warp[i][j+1]:
        f(i, j+1, wc)

    for di in range(max(i-2, 0), min(i+2, h-1)+1):
        for dj in range(max(j-2, 0), min(j+2, w-1)+1):
            if s[di][dj] == '.' and wc + 1 < warp[di][dj]:
                f(di, dj, wc+1)


h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = []
warp = [[10000] * w for i in range(h)]
for i in range(h):
    s.append(input())

f(ch-1, cw-1, 0)

if warp[dh-1][dw-1] == 10000:
    print(-1)
else:
    print(warp[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop


class DisjointSet:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def dijkstra(adj_list, start):
    dist = defaultdict(lambda: float("inf"))
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))
    visited = set()
    while pq:
        w, v = heappop(pq)
        if dist[v] < w:
            continue
        visited.add(v)
        for nv, nw in adj_list[v]:
            if nv in visited:
                continue
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq, (dist[nv], nv))
    return dist


def solve():
    H, W = map(int, input().split())
    C_h, C_w = map(lambda x: int(x) - 1, input().split())
    D_h, D_w = map(lambda x: int(x) - 1, input().split())
    field = [list(input()) for _ in range(H)]

    ds = DisjointSet(H * W)
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                continue
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni = i + di
                nj = j + dj
                if 0 <= ni < H and 0 <= nj < W and field[ni][nj] != "#":
                    ds.union(j + i * H, nj + nj * H)

    g = defaultdict(set)
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                continue
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if di == 0 and dj == 0:
                        continue
                        ni = i + di
                        nj = j + dj
                    if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] != "#"):
                        continue
                    if ds.same(j + i * H, nj + ni * H):
                        g[(i, j)].add(((ni, nj), 0))
                        g[(ni, nj)].add(((i, j), 0))
                    else:
                        g[(i, j)].add(((ni, nj), 1))
                        g[(ni, nj)].add(((i, j), 1))

    dist = dijkstra(g, (C_h, C_w))
    ans = dist[(D_h, D_w)]
    print(-1) if ans == float("inf") else print(ans)


solve()

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x)-1, input().split())
    d_h, d_w = map(lambda x: int(x)-1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [[] for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    if j + m < 0 or area_cnt <= j + m:
                        continue
                    if area[i + k][j + m] is None:
                        continue
                    if area[i][j] != area[i + k][j + m]:
                        can_move[area[i][j]].append(area[i + k][j + m])
                        can_move[area[i + k][j + m]].append(area[i][j])
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

h, w, m = map(int, input().split(' '))
H = [0 for _ in range(h+1)]
W = [0 for _ in range(w+1)]
bomb = set()
for m in range(m):
  i, j = map(int, input().split(' '))
  bomb.add((i, j))
  H[i] += 1
  W[j] += 1
  
max_h = max(H)
max_w = max(W)
target_h = [i for i, v in enumerate(H) if v == max_h]
target_w = [i for i, v in enumerate(W) if v == max_w]

for m in target_h:
  for n in target_w:
    if (m, n) not in bomb:
      print(max_h + max_w)
      sys.exit()
	
print(max_h + max_w - 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def main():
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[float("inf")] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(_h, _w, warp):
        warp_count[_h][_w] = min(warp, warp_count[_h][_w])
        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                dfs(_h + _a, _w + _b, warp)
        # warp
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x, y) in directions:
                    continue
                elif x == 0 and y == 0:
                    continue
                if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                    continue
                if grid[_h + x][_w + y] == "#":
                    continue
                if warp_count[_h + x][_w + y] > warp + 1:
                    dfs(_h + x, _w + y, warp + 1)

    dfs(c_h, c_w, 0)
    if warp_count[d_h][d_w] == float("inf"):
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
C_L = [int(_)-1 for _ in input().split()]
D_L = [int(_)-1 for _ in input().split()]
S_L = [[x for x in input()] for y in range(H)]


ans = 0
c_l = [[float("Inf")] * W for _ in range(H)]


def dfs(x, y, c):
    if not(0 <= x < W) or not(0 <= y < H) or S_L[y][x] == "#":
        return
    if c_l[y][x] > c:
        c_l[y][x] = c

        # no magic
        dfs(x+1, y, c)
        dfs(x-1, y, c)
        dfs(x, y+1, c)
        dfs(x, y-1, c)

        # use magic
        for _x in range(-2, 3):
            for _y in range(-2, 3):
                if (_x == -1 and _y == 0) or (_x == 1 and _y == 0) or (_x == 0 and _y == -1)or (_x == 0 and _y == 1) or (_x == 0 and _y == 0):
                    continue
                dfs(x+_x, y+_y, c+1)


dfs(C_L[1], C_L[0], 0)

if c_l[D_L[0]][D_L[1]] == float("Inf"):
    print("-1")
else:
    print(c_l[D_L[0]][D_L[1]])

Submission status: Runtime Error

Solution code:
import collections

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


color = 0
def paint(grid, colors):
    global color
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.' and colors[y][x] == UNDEF:
                q = collections.deque()
                colors[y][x] = color
                q.append((y, x))
                while q:
                    i, j = q.popleft()

                    for ii, jj in (
                        (i - 1, j),
                        (i, j - 1),
                        (i, j + 1),
                        (i + 1, j)
                    ):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                            colors[ii][jj] = color
                            q.append((ii, jj))
                color += 1

paint(grid, colors)


def build(grid, colors, ncolors):
    g = [set() for _ in range(ncolors)]
    for i in range(h):
        for j in range(w):
            if colors[i][j] != UNDEF:
                for ii in range(i - 2, i + 3):
                    for jj in range(j - 2, j + 3):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                            c1 = colors[ii][jj]
                            c2 = colors[i][j]
                            assert c1 != UNDEF and c2 != UNDEF
                            g[c1].add(c2)
                            g[c2].add(c1)
    return g

g = build(grid, colors, color)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def main():
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[float("inf")] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(_h, _w, warp):
        warp_count[_h][_w] = min(warp, warp_count[_h][_w])
        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                dfs(_h + _a, _w + _b, warp)
        # warp
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x, y) in directions:
                    continue
                elif x == 0 and y == 0:
                    continue
                if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                    continue
                if grid[_h + x][_w + y] == "#":
                    continue
                if warp_count[_h + x][_w + y] > warp + 1:
                    dfs(_h + x, _w + y, warp + 1)

    dfs(c_h, c_w, 0)
    if warp_count[d_h][d_w] == float("inf"):
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


H, W = list(map(int, input().split()))
Ch, Cw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
S = [input() for _ in range(H)]

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

f = [[False] * W for _ in range(H)]
from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(i, j):
  dprint(i, j)
  dprint(f)
  if not (0 <= i < H and 0 <= j < W):
    return None
  if f[i][j]:
    return None
  f[i][j] = True
  if S[i][j] == '#':
    return None
  if i == Dh and j == Dw:
    return 0
  rets = set()
  for di in (-1, 1):
    rets.add(dfs(i + di, j))
  for dj in (-1, 1):
    rets.add(dfs(i, j + dj))

  for wi in range(-2, 2 + 1):
    for wj in range(-2, 2 + 1):
      try:
        rets.add(1 + dfs(i + wi, j + wj))
      except TypeError:
        pass
  # rets = set(rets)
  rets.add(None)
  rets.remove(None)
  dprint(rets)
  if len(rets) == 0:
    return None
  # f[i][j] = min(rets)
  # return f[i][j]
  return min(rets)


# f[Ch][Cw] = 0

ans = dfs(Ch, Cw)
if ans is None:
  print('-1')
else:
  print(ans)

Submission status: Runtime Error

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(2,H+2):
    for w in range(2,W+2):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            assert neigh!=-1
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
else:
    print(dist[goal])
    assert dist[goal]==-1

Submission status: Runtime Error

Solution code:
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args){
        int H = in.i();
        int W = in.i();
        int Ch = in.i() - 1;
        int Cw = in.i() - 1;
        int Dh = in.i() - 1;
        int Dw = in.i() - 1;
        char[][] S = new char[H][];
        boolean[][] visited = new boolean[H][W];
        for (int i = 0; i < H; i++) {
            S[i] = in.s(W);
        }
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> possible = new ArrayList<>();
        list.add((Ch << 10) + Cw);
        int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int count = 0;
        int ans = -1;
        visited[Ch][Cw] = true;
        loop: while (list.size() > 0) {
            possible.addAll(list);
            while (list.size() > 0) {
                int hw = list.pop();
                int h = hw >> 10;
                int w = hw & ((1 << 10) - 1);

                for (int[] ij : d) {
                    int h2 = h + ij[0];
                    int w2 = w + ij[1];
                    boolean isRoad = 0 <= h2 && h2 < H && 0 <= w2 && w2 < W && S[h2][w2] == '.';
                    if (isRoad && !visited[h2][w2]) {
                        int n = (h2 << 10) + w2;
                        possible.add(n);
                        list.add(n);
                        visited[h2][w2] = true;
                    }
                }
                if (visited[Dh][Dw]) {
                    ans = count;
                    break loop;
                }
            }

            for (int hw : possible) {
                int h = hw >> 10;
                int w = hw & ((1 << 10) - 1);
                for (int i = -2; i < 3; i++) {
                    for(int j = -2; j < 3; j++) {
                        int h2 = h + i;
                        int w2 = w + j;
                        boolean isRoad = 0 <= h2 && h2 < H && 0 <= w2 && w2 < W && S[h2][w2] == '.';
                        if (isRoad && !visited[h2][w2]) {
                            list.add((h2 << 10) + w2);
                            visited[h2][w2] = true;
                        }
                    }
                }
            }
            count++;
            if (visited[Dh][Dw]) {
                ans = count;
                break;
            }
            possible.clear();
        }
        out.println(ans);
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = read(cbuf, 0, cbuf.length);
            } catch (IOException e) {}
            head = 0;
        }
        return cbuf[head++];
    }

    void back() {
        head--;
    }

    boolean minus() {
        boolean minus;
        while (true) {
            char c = next();
            if (c != ' ' && c != '\n' && c != '\r') {
                if (!(minus = c == '-')) back();
                return minus;
            }
        }
    }

    void skip() {
        while (true) {
            char c = next();
            if (c != ' ' && c != '\n' && c != '\r') {
                back();
                break;
            }
        }
    }

    char[] s(final int N) {
        skip();
        char[] s = new char[N];
        for (int i = 0; i < s.length; i++) {
            s[i] = next();
        }
        return s;
    }

    int i() {
        boolean minus = minus();
        int n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        boolean minus = minus();
        long n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }
}