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:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ list(sys.stdin.readline().strip()) for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for idx in range(H):
    S.append(list(input()))

# 移動できるstep
step_list = [(-1, 0), (0, -1), (1, 0), (0, 1)]
# ワープで移動できる距離
warp_list = [(x, y) for x in range(-2 ,3) for y in range(-2, 3)]
warp_list.remove((0, 0))
for step in step_list:
    warp_list.remove(step)

# ワープ使用回数 -1は未探索 
seen = [[-1] * W for x in range(H)]

def search_step_dfs(see_x, see_y, warp_cnt):
    seen[see_x][see_y] = warp_cnt
    
    for step_x, step_y in step_list:
        try_x = see_x + step_x
        try_y = see_y + step_y
        if not(0 <= try_x < H and 0 <= try_y < W):
            continue # 範囲外
        if seen[try_x][try_y] != -1 and seen[try_x][try_y] <= warp_cnt:
            continue # より少ないワープで探索済
        if S[try_x][try_y] == '#':
            continue # 進入不可
        search_step_dfs(try_x, try_y, warp_cnt)
    
    for warp_x, warp_y in warp_list:
        try_x = see_x + warp_x
        try_y = see_y + warp_y
        if not(0 <= try_x < H and 0 <= try_y < W):
            continue # 範囲外
        if seen[try_x][try_y] != -1 and seen[try_x][try_y] <= warp_cnt:
            continue # より少ないワープで探索済
        if S[try_x][try_y] == '#':
            continue # 進入不可
        search_step_dfs(try_x, try_y, warp_cnt + 1)

# 初期位置から移動できるマスを探索
search_step_dfs(Ch - 1, Cw - 1, 0)

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

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())

C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[10000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy
        if cost[y][x] == cost[ny][nx]:
            continue

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if cost[y][x] == cost[ny][nx]:
            continue

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
    flg[y][x] = 1
answer = cost[D[0]-1][D[1]-1]
if answer == 10000:
    print(-1)
else:
    print(answer)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
amap = []
for _ in range(h):
  amap.append([ s for s in input()])
posh = ch - 1
posw = cw - 1
time = 0
ans = 10000
mva = [ (0,1), (1,0), (0,-1), (-1,0) ]
mvb = [ (-2,2), (-1,2), (0,2), (1,2), (2,2), 
        (-2, 1), (-1, 1), (1, 1), (2, 1), 
       (-2, 0), (2, 0),
       (-2, -1), (-1, -1), (1, -1), (2, -1), 
      (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2),
      ]
def possible(x, y):
  if x<0 or x>=h or y<0 or y>=w:
    return False
  if amap[x][y] == '#':
    return False
  if amap[x][y] == '.':
    return True

def dfs(posh, posw, time):
  global ans
  if posh == (dh-1) and posw == (dw-1):
    if time < ans:
      ans = time
  amap[posh][posw] = '#'
  for x, y in mva:
    if possible(posh+x,posw+y):
      dfs(posh+x, posw+y, time)
  for x, y in mvb:
    if possible(posh+x,posw+y):
      time = time + 1
      dfs(posh+x, posw+y, time)
  
      
dfs(posh, posw, time)
if ans == 10000:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:

from collections import deque

N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1


S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx






for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]



seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合


dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]


def dfs(y,x):

    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        count+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]
                    #print(seen)
                    return seen[ny][nx]
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                
                    
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
    

            
    return seen[ny][nx]

            
print(dfs(starty,startx))

Submission status: Runtime Error

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

import numpy as np
from itertools import permutations

class Lab:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.map = np.zeros(shape=(h, w), dtype=np.int8)
        self.max_c = 1
        self.tree = dict()

    def set_wall(self, ih, walls):
        self.map[ih] = walls

    def bfs(self, y, x, c):
        self.map[y][x] = c

        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = y+dy, x+dx
            if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                continue
            if self.map[ny][nx] != 0:
                continue
            self.bfs(ny, nx, c)

    def coloring(self):
        for y in range(self.h):
            for x in range(self.w):
                if self.map[y][x] == 0:
                    self.max_c += 1
                    self.bfs(y, x, self.max_c)

    def room(self):
        if self.max_c == 1:
            return

        for c in range(2, self.max_c+1):
            self.tree[c] = set()

        for y in range(self.h):
            for x in range(self.w):
                c = self.map[y][x]
                if c == 1:
                    continue
                for dy in range(-2, 3):
                    for dx in range(-2, 3):
                        ny, nx = y + dy, x + dx
                        if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                            continue
                        tc = self.map[ny][nx]
                        if tc not in (1, c):
                            self.tree[c].add(tc)


def solve():
    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

    lab = Lab(h, w)
    for i in range(h):
        walls = np.array(list(map(lambda x: int(x == "#"), input())))
        lab.set_wall(i, walls)

    lab.coloring()
    # print(lab.map)
    dc = lab.map[dh][dw]
    if dc == 1:
        return "-1"

    cc = lab.map[ch][cw]
    if dc == cc:
        return 0

    lab.room()
    # print(lab.tree)
    ct = lab.tree[cc]
    if dc in ct:
        return 1

    lab.tree.pop(cc)
    pre_set = ct
    min_dist = 10 ** 9
    for roots in permutations(lab.tree):
        # print(roots)
        dist = 0
        ok = False
        for nc in roots:
            if nc not in pre_set:
                break
            dist += 1
            if dc in pre_set:
                ok = True
                break
            pre_set = lab.tree[nc]
        if ok:
            min_dist = min(min_dist, dist)

    if min_dist == 10 ** 9:
        return "-1"

    return min_dist


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
cx, cy = list(map(int, input().split()))
dx, dy = list(map(int, input().split()))
cx -= 1
cy -= 1
dx -= 1
dy -= 1

m = []

for i in range(h):
    s = input()
    lis = [0 if c == '.' else -1 for c in s]
    m.append(lis)

def is_not_road(x, y):
    return x < 0 or x >= h or y < 0 or y >= w or m[x][y] < 0

def paint(x, y, c):
    global m
    if is_not_road(x, y): return

    if m[x][y] == 0:
        m[x][y] = c
    elif m[x][y] <= c:
        return
    else:
        m[x][y] = c

    paint(x - 1, y, c)
    paint(x + 1, y, c)
    paint(x, y - 1, c)
    paint(x, y + 1, c)

    for i in range(-2, 3):
        for j in range(-2, 3):
            paint(x + i, y + j, c + 1)

paint(cx, cy, 1)

if m[dx][dy] > 0:
    print(m[dx][dy] - 1)
else:
    print(-1)

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 = [set([]) 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]].add(area[i + k][j + m])
                        can_move[area[i + k][j + m]].add(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:
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 0 <= y+i+k < R and 0 <=  x+j+l < C:
          if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1 and warp[y+i+k][x+j+l] == 0:
            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:
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
M=[list(input()) for _ in range(h)]
D=[[10000]*w for _ in range(h)]
D[ch-1][cw-1]=0
q=[]
q.insert(0,(ch-1,cw-1))
while q:
  y,x=q.pop()
  M[y][x]='#'
  if y==dh-1 and x==dw-1:
    continue
  for i in range(4):
    ny,nx=y+[1,0,-1,0][i],x+[0,1,0,-1][i]
    if 0<=nx and nx<w and 0<=ny and ny<h and M[ny][nx]=='.' and D[ny][nx]>=D[x][y]:
      q.insert(0,(ny,nx))
      D[ny][nx]=min(D[x][y],D[ny][nx])
  for i in range(-2,3):
    for j in range(-2,3):
      if i!=0 and j!=0:
        ny,nx=y+i,x+j
        if 0<=nx and nx<w and 0<=ny and ny<h and M[ny][nx]=='.' and D[ny][nx]>=D[x][y]:
          q.insert(0,(ny,nx))
          D[ny][nx]=min(D[y][x]+1,D[ny][nx])
print(D[dh-1][dw-1] if D[dh-1][dw-1]!=10000 else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append([CY, CX])  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
# print(distant)
# 更新されるなら追加
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == ".":
            # 道の場合はコスト0で移動できる
            if distant[ny][nx] > distant[cy][cx]:
                distant[ny][nx] = distant[cy][cx]
                q.append([ny, nx])
    # 周囲5*5の道に+1で到達する
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append([target_y, target_x])

if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Runtime Error

Solution code:

from collections import deque

N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1


S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx






for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]



seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合


dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]


def dfs(y,x):

    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        count+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]
                    #print(seen)
                    return seen[ny][nx]
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                
                    
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
    

            
    return seen[ny][nx]

            
print(dfs(starty,startx))

Submission status: Runtime Error

Solution code:
import sys
H,W = map(int,input().split())
cH,cW = map(int,input().split())
dH,dW = map(int,input().split())
m = [list(input()) for _ in range(H)]
jud = []
cnt = []
def abc(n):
    n += 1
    return
def dfs(x,y):
    if not (0 <= x < H) or not (0 <= y < W) :
        return
    if m[x][y] == "#":
        return
    if x == dH-1 and y == dW-1:
        print(len(cnt))
        sys.exit()
    
    m[x][y] = '#'

    dfs(x+1,y)
    dfs(x,y+1)
    dfs(x-1,y)
    dfs(x,y-1)

    cnt.append(1)
    for a in range(-2,3):
        for b in range(-2,3):
            dfs(x+a,y+b)

dfs(cH-1,cW-1)
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W=map(int,input().split())
Sx,Sy=map(int,input().split())
Gx,Gy=map(int,input().split())
Sx-=1
Sy-=1
Gx-=1
Gy-=1
tmp=False

M=[[0 if j=='.' else 1 for j in input()]for i in range(H)]

# 0通路 1壁 2確認済み

ans=0
check.append([Sx,Sy])
while True:
    hit=set()
    while check:
        x,y = check.pop()
        #goul
        if x==Gx and y==Gy:
            tmp=True
            break
        M[x][y]=2
        #壁があるか
        for dx,dy in [ [x+1,y],[x-1,y],[x,y-1],[x,y+1] ]:
            if not(0<=dx and dx<H and 0<=dy and dy<W):
                continue
            if M[dx][dy]==1:
                hit.add((x,y))
            if M[dx][dy]==0:
                check.append([dx,dy])
    if tmp:
        print(ans)
        break
    if len(hit)==0:
        print(-1)
        break
    for e in hit:
        x,y=e
        for i in range(-2,3):
            for j in range(-2,3):
                if 0<=x+i and x+i<H and 0<=y+j and y+j<W and M[x+i][y+j]==0:
                    check.append([x+i,y+j])
    if len(check)==0:
        print(-1)
        break

    ans+=1

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
h,w = list(map(int,input().split()))
ch,cw = list(map(int,input().split()))
dh,dw = list(map(int,input().split()))
d = [["#","#"] + list(input())  + ["#","#"] for i in range(h)]
d = [["#"] * (w+4)] * 2 + d + [["#"] * (w+4)] * 2
def bfs(h,w,cnt=0):
    if d[h][w]==".":
        d[h][w]=cnt
        bfs(h+1,w,cnt)
        bfs(h-1,w,cnt)
        bfs(h,w+1,cnt)
        bfs(h,w-1,cnt)

cnt = 0
for i in range(h+4):
    for j in range(w+4):
        if d[i][j]==".":
            bfs(i,j,cnt)
            cnt+=1

can_move_area = [set() for _ in range(cnt)]

for i in range(h+2):
    for j in range(w+2):
        a = d[i][j]
        if a != "#":
            b = d[i-2][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-2][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-1][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-1][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+1][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+1][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)

from copy import copy
can_move = copy(can_move_area)
for i,v in enumerate(can_move_area):
    for j in v:
        can_move[j].add(i)

start_area = d[ch+1][cw+1]
goal_area = d[dh+1][dw+1]

cost_from_start_area = [-1] * cnt
cost_from_start_area[start_area] = 0
def area_bfs(area_id,cost):
    global cost_from_start_area
    next_areas = can_move[area_id]
    next_b = []
    for ai in next_areas:
        if cost_from_start_area[ai]==-1:
            cost_from_start_area[ai] = cost+1
            next_b.append(ai)
    for ai in next_b:
        area_bfs(ai,cost+1)

area_bfs(start_area,0)

print(cost_from_start_area[goal_area])

Submission status: Runtime Error

Solution code:
from collections import namedtuple, deque

Point = namedtuple('Point', ['x', 'y'])

H, W = map(int, input().split())
C_y, C_x = Point(*map(lambda x: int(x) - 1, input().split()))
D_y, D_x = Point(*map(lambda x: int(x) - 1, input().split()))
C = Point(C_x, C_y)
D = Point(D_x, D_y)
S = []

for _ in range(H):
    line = input()
    S.append([*line])

warp_num = 0

vx = [1, -1, 0, 0]
vy = [0, 0, 1, -1]

def search_warp_point(seen, pos):
    candidate_point = None
    for vy in range(-2, 2 + 1):
        for vx in range(-2, 2 + 1):
            x = pos.x + vx
            y = pos.y + vy
            if not 0 <= x < W or not 0 <= y < H:
                continue
            if x == D.x and y == D.y:
                return 1
            if seen[y][x] == False and S[y][x] == '.' and candidate_point is None:
                candidate_point = Point(x, y)
    return candidate_point

def dump(seen):
    for y in range(H):
        for x in range(W):
            c = "@" if seen[y][x] else S[y][x]
            print(c, end="")
        print()
    print()

def dfs(C, warp_num=0, seen=None):
    sx, sy = C
    if seen is None:
        seen = [[False] * W for _ in range(H)]
    seen[sy][sx] = True
    visit = [Point(sx, sy)]
    todo = [(sx, sy)]

    while len(todo) != 0:
        pos = todo.pop(0)
        for i in range(4):
            x = pos[0] + vx[i]
            y = pos[1] + vy[i]
            if x == D.x and y == D.y:
                return warp_num
            if not 0 <= x < W or not 0 <= y < H:
                continue
            #dump(seen)
            if seen[y][x] or S[y][x] == "#": continue
            seen[y][x] = True
            visit.append(Point(x, y))
            todo.append((x, y))
    for p in visit: 
        x, y = p
        next_point = search_warp_point(seen, Point(x, y))
        if next_point is None:
            continue
        if isinstance(next_point, int):
            return warp_num + 1
        else:
            warp_num += 1
            return dfs(next_point, warp_num=warp_num, seen=seen)
    return -1

print(dfs(C))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch , cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
fl = [[100000 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j:j+1] == "#"):
            fl[i][j] = -1

fl[ch-1][cw-1] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1,  2,  2, 2, 2, 2]
ddy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
que = [[ch-1, cw-1]]
while(len(que) != 0):
    now = que.pop(0)
    x, y = now[0], now[1]
    for i in range(4):
        if((x+dx[i] >= 0) and (x+dx[i] >= 0)):
            if(fl[x+dx[i]][x+dx[i]] >= 0):
                if(fl[x+dx[i]][x+dx[i]] > 1000):
                    que.append([x+dx[i], y+dy[i]])
                fl[x+dx[i]][x+dx[i]] = min(fl[x][y], fl[x+dx[i]][x+dx[i]])
                
    for i in range(20):
        if((x+ddx[i] >= 0) and (x+ddx[i] >= 0)):
            if(fl[x+ddx[i]][x+ddx[i]] >= 0):
                if(fl[x+dx[i]][x+dx[i]] > 1000):
                    que.append([x+dx[i], y+dy[i]])
                fl[x+ddx[i]][x+ddx[i]] = min(fl[x][y], fl[x+ddx[i]][x+ddx[i]])+1
    que = list(map(que))
print(fl[dh][dw])

Submission status: Runtime Error

Solution code:
h, w = [int(w) for w in input().split()]
ch, cw = [int(w)-1 for w in input().split()]
dh, dw = [int(w)-1 for w in input().split()]

field = [list(input()) for _ in range(h)]
warp = [[1, 1, 1, 1, 1], [1, 1, 0, 1, 1], [
    1, 0, 0, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1]]

cost = [[1e10]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            cost[i][j] = 1e10

# N E S W
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
now_dir = 0


def step(_h, _w, _c):
    if _c >= cost[_h][_w]:
        return
    cost[_h][_w] = _c

    # 4
    for d in direction:
        if _h+d[0] < 0 or _h+d[0] >= h or _w+d[1] < 0 or _w+d[1] >= w:
            continue
        if field[_h+d[0]][_w+d[1]] == ".":
            step(_h+d[0], _w+d[1], _c)

    # syuui
    for i in range(-2, 3):
        if _h+i < 0 or _h+i >= h:
            continue
        for j in range(-2, 3):
            if _w+j < 0 or _w+j >= w:
                continue
            if warp[i][j] == 0:
                continue
            if field[_h+i][_w+j] == ".":
                step(_h+i, _w+j, _c+1)


step(dh, dw, 0)

if cost[ch][cw] == 1e10:
    print(-1)
else:
    print(cost[ch][cw])

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):
      d = dfs(i + wi, j + wj)
      if d is not None:
        rets.add(1 + d)

  rets.add(None)
  rets.remove(None)
  dprint(rets)
  if len(rets) == 0:
    return None
  return min(rets)


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