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:

import datetime
from decimal import Decimal, ROUND_DOWN
import heapq
from fractions import gcd
from functools import reduce
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import statistics
# import numpy as np
# n = int(input())
# n, m, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
#
#  abc = [int(input()) for i in range(5)]
# n = int(input())
h, w = list(map(int, input().split()))
Ch, Cw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# l = list(map(int, input().split()))
# r = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
# data = [list(map(int, input().split())) for i in range(n)]
# print(min(15*n, 100*(n//10+1), 100*(n//10)+15*(n % 10)))
# for i in range(1, int(n**0.5)+1):
s = [input() for i in range(h)]

# print(s)

d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = deque()
count = [[0 for j in range(w)] for i in range(h)]
mark = 1
"""
for i in range(h):
    for j in range(w):
        print(count[i][j], end="")
    print()
"""
for i in range(h):
    for j in range(w):
        if s[i][j] == "." and count[i][j] == 0:
            # print(str(i)+","+str(j))
            q.append([i, j])  # (x, y)
            count[i][j] = mark
            # search
            while q:
                y, x = q.popleft()
                for i in range(4):
                    nx, ny = x+d[i][1], y+d[i][0]
                    if 0 <= ny and ny < h and 0 <= nx and nx < w and s[ny][nx] == "." and count[ny][nx] == 0:
                        count[ny][nx] = mark
                        q.append([ny, nx])
            mark += 1
"""
for i in range(h):
    for j in range(w):
        print(count[i][j], end="")
    print()
"""

if count[Ch-1][Cw-1] == count[Dh-1][Dw-1]:
    print(0)
    exit()

path = []
for i in range(h):
    for j in range(w):
        if count[i][j] != 0:
            for k in range(max(0, i-2), min(h, i+2)):
                for l in range(max(0, j-2), min(w, j+2)):
                    if count[k][l] != 0 and count[k][l] != count[i][j]:
                        path.append([count[k][l], count[i][j]])

# print(path)
pair = [[] for i in range(mark-1)]
for i in range(len(path)):
    if not(path[i][1] in pair[path[i][0]-1]):
        pair[path[i][0]-1].append(path[i][1])
    if not(path[i][0] in pair[path[i][1]-1]):
        pair[path[i][1]-1].append(path[i][0])
# print(pair)

start = count[Ch-1][Cw-1]
end = count[Dh-1][Dw-1]

# print(start)
# print(end)

q = []
visited = [0 for i in range(mark-1)]
q.append(start-1)
root = []
while q:
    point = q.pop()
    for i in range(len(pair[point])):
        _next = pair[point][i]
        root.append(_next-1)
        if _next == end:
            print(len(root))
            # print(root)
            exit()
        if visited[_next-1] == 0:
            q.append(_next-1)
print(-1)

Submission status: Runtime Error

Solution code:
h,w = map(int, input().split())
hstart, wstart= map(int, input().split())
hend, wend= map(int, input().split())

matrix= []
for i in range(h):
	matrix.append(list(input())+['#']*20)

for i in range(10):
	matrix.append(['#']*(w+20))

matrix[hstart-1][wstart-1]= 0

#print(matrix)
def check_surrounds(h, w):
	if matrix[h][w]!='.' and matrix[h][w]!='#':
		value= matrix[h][w]
		

		if matrix[h+1][w]!='#':
			if matrix[h+1][w] == '.':
				matrix[h+1][w]= value
				check_surrounds(h+1, w)
			elif matrix[h+1][w]>value:
				matrix[h+1][w]= value
				check_surrounds(h+1, w)
		if matrix[h][w+1]!='#':
			if matrix[h][w+1] == '.':
				matrix[h][w+1]= value
				check_surrounds(h, w+1)
			elif matrix[h][w+1] >value:
				matrix[h][w+1]= value
				check_surrounds(h, w+1)
		if matrix[h-1][w]!='#':		
			if matrix[h-1][w] == '.':
				matrix[h-1][w]= value
				check_surrounds(h-1, w)
			elif matrix[h-1][w] > value:
				matrix[h-1][w]= value
				check_surrounds(h-1, w)
		if matrix[h][w-1] != '#':
			if matrix[h][w-1] == '.':
				matrix[h][w-1]= value
				check_surrounds(h, w-1)
			elif matrix[h][w-1] >value:
				matrix[h][w-1]= value
				check_surrounds(h, w-1)
		for i in range(-2, 3):
			for j in range(-2,3):
		#		print(h+i, w+j)
				if matrix[h+i][w+j]!='#':
					if matrix[h+i][w+j]=='.':
						matrix[h+i][w+j]= value+1
						check_surrounds(h+i,w+j)
					elif matrix[h+i][w+j]>value+1:
						matrix[h+i][w+j]= value+1
						check_surrounds(h+i,w+j)
			

check_surrounds(hstart-1, wstart-1)

if matrix[hend-1][wend-1] == '.':
	print(-1)
else:
	print(matrix[hend-1][wend-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())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = []
for i in range(h):
    s.append(list(input()))


def mn(i, j):
    for a, b in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        if 0 < i + a < h and 0 < j + b < w:
            p = i + a
            q = j + b
            if p != i or q != j:
                if s[p][q] != "#":
                    if s[p][q] == "." or s[p][q] > s[i][j]:
                        s[p][q] = s[i][j]
                        mn(p, q)
    lst = []
    lst.extend([(-2, y) for y in range(-2, 3)])
    lst.extend([(2, y) for y in range(-2, 3)])
    lst.extend([(-1, 0), (0, -1), (0, 1), (1, 0)])
    lst.extend([(1,-2), (0,-2), (1, -2), (2,-2), (2,-2), (2, -2)])
    for a, b in lst:
        if 0 < i + a < h and 0 < j + b < w:
            p = i + a
            q = j + b
            if s[p][q] != "#":
                if s[p][q] == ".":
                    s[p][q] = s[i][j] + 1
                    mn(p, q)
                elif s[p][q] > s[i][j] + 1:
                    s[p][q] = s[i][j] + 1
                    mn(p, q)


s[ch][cw] = 0
mn(ch, cw)

if s[dh][dw] == ".":
    print(-1)
else:
    print(s[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())
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(y, x):
  if x<0 or y>=h or y<0 or x>=w:
    return False
  if amap[y][x] == '#':
    return False
  if amap[y][x] == '.':
    return True

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

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
maze=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)
def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
def update(maze,h,w,value):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=[]
  u=[]
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      if [h+i//5-2,w+i%5-2] not in u:
        u.append([h+i//5-2,w+i%5-2])
        maze[h+i//5-2][w+i%5-2]=value+1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      update(maze,h+vector[0],w+vector[1],value)
      
  for h,w in u:
    if maze[h][w]==value+1 and not [h,w] in update_list:
      update_list.append([h,w])
  return update_list

update_list=update(maze,Ch-1,Cw-1,0)
def calc(update_list):
  for h,w in update_list:
    u=update(maze,h,w,maze[h][w])
    calc(u)
calc(update_list)
print(maze[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

H = 0
W = 0


def search(h, w, table, cnt):
    global H, W

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

    for k in range(len(move)):
        i, j = move[k]
        if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
            continue
        if table[h+i][w+j] == '.':
            table[h+i][w+j] = cnt
            search(h+i, w+j, table, cnt)
        elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt:
            table[h+i][w+j] = cnt
            search(h+i, w+j, table, cnt)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W or(i == 0 and j == 0):
                continue
            if table[h+i][w+j] == '.':
                table[h+i][w+j] = cnt+1
                search(h+i, w+j, table, cnt+1)
            elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt+1:
                table[h+i][w+j] = cnt+1
                search(h+i, w+j, table, cnt+1)


def main(input, print):
    global H, W
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [[] for _ in range(W)]
    for i in range(H):
        table[i] = list(input().strip())
    search(Ch-1, Cw-1, table, 0)
    if(table[Dh-1][Dw-1] == '.'):
        print(-1)
    else:
        print(table[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [input() for _ in range(h)]

# 魔法使わない
dx1 = [1, 0, -1, 0]
dy1 = [0, 1, 0, -1]

# 魔法使う
dx2 = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
dy2 = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]

mp = [[10**9 for _ in range(w)] for _ in range(h)]

walk_visited = [[False for _ in range(w)] for _ in range(h)]

def bfs(x, y):
    for dx, dy in zip(dx1, dy1):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            mp[ny][nx] = min(mp[ny][nx], mp[y][x])

    for dx, dy in zip(dx2, dy2):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            mp[ny][nx] = min(mp[ny][nx], mp[y][x]+1)

    for dx, dy in zip(dx1, dy1):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            if mp[ny][nx] >= mp[y][x] and not walk_visited[y][x]:
                walk_visited[ny][nx] = True
                bfs(nx, ny)
    
    for dx, dy in zip(dx2, dy2):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            if mp[ny][nx] > mp[y][x]:
                bfs(nx, ny)
    

mp[ch-1][cw-1] = 0
bfs(cw-1, ch-1)
if mp[dh-1][dw-1] == 10**9:
    mp[dh-1][dw-1] = -1
print(mp[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque

n , m = map(int, input().split())
ch , cw = map(int, input().split())
dh , dw = map(int, input().split())
maze = [['#','#']+list(input())+['#','#'] for i in range(n)]
maze = [['#']*(m+4)]+[['#']*(m+4)]+maze+[['#']*(m+4)]+[['#']*(m+4)]

step = [(0,1),(1,0),(-1,0),(0,-1)]
warp_u = [(-2,0)]
warp_d = [(2,0)]
warp_r = [(0,2)]
warp_l = [(0,-2)]
warp_ur = [(-1,1)(-2,1),(-2,2),(0,2),(-2,0),(-1,2)]
warp_dr = [(2,0),(2,1),(2,2),(1,1),(1,2),(0,2)]
warp_ul = [(-2,0),(-2,-1),(-2,-2),(-1,-1),(-1,-2),(0,-2)]
warp_dl = [(2,0),(2,-1),(2,-2),(1,-1),(1,-2),(0,-2)]



warp=0

v = [[-1]*(m+4) for i in range(n+4)]
d = deque()
d.append((ch+1,cw+1,0))
v[ch+1][cw+1]=0
while d:
    y,x,wa=d.popleft()
    for dy,dx in step:
        if maze[y+dy][x+dx]=='.' and (v[y+dy][x+dx]==-1 or v[y+dy][x+dx]>wa):
            v[y+dy][x+dx]=wa
            d.append((y+dy,x+dx,wa))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_d:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='#' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='.' and maze[y][x-1]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_r:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='#' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='.' and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_u:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='#' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='.' and maze[y][x-1]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_l:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='#' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='.' and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
print(v[dh+1][dw+1])

Submission status: Runtime Error

Solution code:
#D
from collections import deque
H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch -=1
cw -=1
dh -=1
dw -=1
A= [list(input()) for _ in range(H)]
d= [ [ -1 for _ in range(W) ] for _ in range(H)]
f= [ [ False for _ in range(W) ] for _ in range(H)]
ans=0

v = deque([ [ch,cw] ])
d[ch][cw]=0
f[ch][cw]=True
move = [(1,0),(-1,0),(0,1),(0,-1)]  #y,xの順

while v:
    while v:
        a = v.pop()
        for mv in move:
            y = a[0]+mv[0]
            x = a[1]+mv[1]
            if 0<=y<=H-1 and 0<=x<=W-1:
                if d[y][x]== -1:
                    if A[y][x]==".":
                        d[y][x] = d[a[0]][a[1]]
                        v.append([y,x])
                        if y==dh and x==dw:
                            print(d[y][x])
                            exit()
    else:
        cnt +=1
        for i in range(0,W):
            for j in range(0,H):
                if d[j][i]==-1:
                    if A[j][i]==".":
                        d[j][i]=10**6
                        k = max(j-2,0)
                        l = min(j+2,H-1)
                        m = max(i-2,0)
                        n = min(i+2,W-1)
                        for s in range(m,n+1):
                            for t in range(k,l+1):
                                if d[t][s]>=0:
                                    d[j][i] = min(d[j][i],d[t][s]+1)
                        if d[j][i]==10**6:
                            d[j][i]=-1
                        else:
                            v.append([j,i])
                            if j==dh and i==dw:
                                print(d[j][i])
                                exit()
else:
    print(-1)

Submission status: Runtime Error

Solution code:
def ispossible(i,j):
    if i<0 or j<0 or i>=n or j>=m or a[i][j]=='#':
        return False
    return True
def func(i,j):
    v[i][j]=1
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j])
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
    for k1 in range(-2,3):
        for k2 in range(-2,3):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j]+1)
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
n,m=[int(i) for i in raw_input().split()]
x1,y1=[int(i)-1 for i in raw_input().split()]
x2,y2=[int(i)-1 for i in raw_input().split()]
dp=[[10**9 for i in range(m)]for j in range(n)]
a=[[i for i in raw_input()]for j in range(n)]
v=[[0 for i in range(m)]for j in range(n)]
dp[x1][y1]=0
func(x1,y1)
if(dp[x2][y2]==10**9):
    print -1
else:
    print dp[x2][y2]

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 = ['#' * (H + 4)]
S.append('#' * (H + 4))
for _ in range(H):
    S.append('##' + input() + '##')
S.append('#' * (H + 4))
S.append('#' * (H + 4))

mapping = [[-1] * (W + 4) for _ in range(H + 4)]

Ch = Ch + 1
Cw = Cw + 1
Dh = Dh + 1
Dw = Dw + 1


def dfs_0(i, j):
    if S[i][j] == '#' or mapping[i][j] != -1:
        return
    mapping[i][j] = 0
    dfs_0(i - 1, j)
    dfs_0(i + 1, j)
    dfs_0(i, j - 1)
    dfs_0(i, j + 1)


dfs_0(Ch, Cw)

near = [[1, 0], [-1, 0], [0, 1], [0, -1]]
warp = [[-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]]
flag = [0]


def dfs(i, j):
    if S[i][j] == '#' or mapping[i][j] != -1:
        return
    for n in range(4):
        if mapping[i + near[n][0]][j + near[n][1]] != -1:
            mapping[i][j] = mapping[i + near[n][0]][j + near[n][1]]
            flag[0] = 0
            break
    if mapping[i][j] == -1:
        for n in range(20):
            if mapping[i + warp[n][0]][j + warp[n][1]] != -1:
                mapping[i][j] = mapping[i + warp[n][0]][j + warp[n][1]] + 1
                flag[0] = 0
                break
    if mapping[i][j] == -1:
        return
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)


while mapping[Dh][Dw] == -1 and flag[0] == 0:
    flag[0] = 1
    for i in range(2, H + 2):
        for j in range(2, W + 2):
            dfs(i, j)

print(mapping[Dh][Dw])

Submission status: Runtime Error

Solution code:
dp = []

def checkcost(h, w):
    if h - 1 > -1:
        if (dp[h - 1][w] == -1 or dp[h - 1][w] > dp[h][w] ) and maiz[h-1][w]=="." :
            dp[h - 1][w] = dp[h][w]
            checkcost(h - 1, w)

    if w - 1 > -1:
        if (dp[h][w - 1] == -1 or dp[h][w - 1] > dp[h][w] ) and maiz[h][w-1]==".":
            dp[h][w - 1] = dp[h][w]
            checkcost(h, w - 1)

    if h + 1 < maxh:
        if (dp[h + 1][w] == -1 or dp[h + 1][w] > dp[h][w] ) and maiz[h+1][w]==".":
            dp[h + 1][w] = dp[h][w]
            checkcost(h + 1, w)

    if w + 1 < maxw:
        if (dp[h][w + 1] == -1 or dp[h][w + 1] > dp[h][w] ) and maiz[h][w+1]==".":
            dp[h][w + 1] = dp[h][w]
            checkcost(h, w + 1)




    if h - 2 > -1:
        if (dp[h - 2][w] == -1 or dp[h - 2][w] > dp[h][w] + 1) and maiz[h-2][w]==".":
            dp[h - 2][w] = dp[h][w] +1
            checkcost(h - 2, w)

    if w - 2 > -1:
        if (dp[h][w - 2] == -1 or dp[h][w - 2] > dp[h][w] + 1) and maiz[h][w-2]==".":
            dp[h][w - 2] = dp[h][w] +1
            checkcost(h, w - 2)

    if h + 2 < maxh:
        if (dp[h + 2][w] == -1 or dp[h + 2][w] > dp[h][w] + 1) and maiz[h+2][w]==".":
            dp[h + 2][w] = dp[h][w] +1
            checkcost(h + 2, w)

    if w + 2 < maxw:
        if (dp[h][w + 2] == -1 or dp[h][w + 2] > dp[h][w] + 1) and maiz[h][w+2]==".":
            dp[h][w + 2] = dp[h][w] +1
            checkcost(h, w + 2)


    if h - 1 > -1 and w - 1 > -1:
        if (dp[h - 1][w-1] == -1 or dp[h - 1][w-1] > dp[h][w] + 1) and maiz[h-1][w-1]==".":
            dp[h - 1][w-1] = dp[h][w] +1
            checkcost(h - 1, w-1)

    if h - 1 > -1 and w + 1 < maxw:
        if (dp[h - 1][w+1] == -1 or dp[h - 1][w+1] > dp[h][w] + 1) and maiz[h-1][w+1]==".":
            dp[h - 1][w+1] = dp[h][w] +1
            checkcost(h - 1, w+1)

    if h + 1 < maxh and w - 1 > -1:
        if (dp[h + 1][w-1] == -1 or dp[h + 1][w-1] > dp[h][w] + 1) and maiz[h+1][w-1]==".":
            dp[h + 1][w-1] = dp[h][w] +1
            checkcost(h + 1, w-1)

    if h + 1 < maxh and w + 1 < maxw:
        if (dp[h + 1][w+1] == -1 or dp[h + 1][w+1] > dp[h][w] + 1) and maiz[h+1][w+1]==".":
            dp[h + 1][w+1] = dp[h][w] +1
            checkcost(h + 1, w+1)


    if h - 2 > -1 and w - 1 > -1:
        if (dp[h - 2][w-1] == -1 or dp[h - 2][w-1] > dp[h][w] + 1) and maiz[h-2][w-1]==".":
            dp[h - 2][w-1] = dp[h][w] +1
            checkcost(h - 2, w-1)

    if h - 2 > -1 and w + 1 < maxw:
        if (dp[h - 2][w+1] == -1 or dp[h - 2][w+1] > dp[h][w] + 1) and maiz[h-2][w+1]==".":
            dp[h - 2][w+1] = dp[h][w] +1
            checkcost(h - 2, w+1)

    if h + 2 < maxh and w - 1 > -1:
        if (dp[h + 2][w-1] == -1 or dp[h + 2][w-1] > dp[h][w] + 1) and maiz[h+2][w-1]==".":
            dp[h + 2][w-1] = dp[h][w] +1
            checkcost(h + 2, w-1)

    if h + 2 < maxh and w + 1 < maxw:
        if (dp[h + 2][w+1] == -1 or dp[h + 2][+1] > dp[h][w] + 1) and maiz[h+2][w+1]==".":
            dp[h + 2][w+1] = dp[h][w] +1
            checkcost(h + 2, w+1)



    if h - 1 > -1 and w - 2 > -1:
        if (dp[h - 1][w-2] == -1 or dp[h - 1][w-2] > dp[h][w] + 1) and maiz[h-1][w-2]==".":
            dp[h - 1][w-2] = dp[h][w] +1
            checkcost(h - 1, w-2)

    if h - 1 > -1 and w + 2 < maxw:
        if (dp[h - 1][w+2] == -1 or dp[h - 1][w+2] > dp[h][w] + 1) and maiz[h-1][w+2]==".":
            dp[h - 1][w+2] = dp[h][w] +1
            checkcost(h - 1, w+2)

    if h + 1 < maxh and w - 2 > -1:
        if (dp[h + 1][w-2] == -1 or dp[h + 1][w-2] > dp[h][w] + 1) and maiz[h+1][w-2]==".":
            dp[h + 1][w-2] = dp[h][w] +1
            checkcost(h + 1, w-2)

    if h + 1 < maxh and w + 2 < maxw:
        if (dp[h + 1][w+2] == -1 or dp[h + 1][w+2] > dp[h][w] + 1) and maiz[h+1][w+2]==".":
            dp[h + 1][w+2] = dp[h][w] +1
            checkcost(h + 1, w+2)





    if h - 2 > -1 and w - 2 > -1:
        if (dp[h - 2][w-2] == -1 or dp[h - 2][w-2] > dp[h][w] + 1) and maiz[h-2][w-2]==".":
            dp[h - 2][w-2] = dp[h][w] +1
            checkcost(h - 2, w-2)

    if h - 2 > -1 and w + 2 < maxw:
        if (dp[h - 2][w+2] == -1 or dp[h - 2][w+2] > dp[h][w] + 1) and maiz[h-2][w+2]==".":
            dp[h - 2][w+2] = dp[h][w] +1
            checkcost(h - 2, w+2)

    if h + 2 < maxh and w - 2 > -1:
        if (dp[h + 2][w-2] == -1 or dp[h + 2][w-2] > dp[h][w] + 1) and maiz[h+2][w-2]==".":
            dp[h + 2][w-2] = dp[h][w] +1
            checkcost(h + 2, w-1)

    if h + 2 < maxh and w + 2 < maxw:
        if (dp[h + 2][w+2] == -1 or dp[h + 2][w+2] > dp[h][w] + 1) and maiz[h+2][w+2]==".":
            dp[h + 2][w+2] = dp[h][w] +1
            checkcost(h + 2, w+2)



if __name__ == '__main__':
    maxh, maxw = map(int, input().split())
    c1, c2 = map(int, input().split())
    d1, d2 = map(int, input().split())

    maiz = []
    dp =[]

    for i in range(maxh):
        s = input()
        maiz.append(s)
        dp.append([-1]*maxw)
    dp[c1-1][c2-1]=0

    checkcost(c1-1,c2-1)
    print(dp[d1-1][d2-1])

Submission status: Runtime Error

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
from collections import deque
mod = 10**9 + 7

def main():
  h, w = I()
  ch, cw = I()
  dh, dw = I()
  s = ['$'*(w+4)]*(h+4)
  for i in range(h):
    s[i+2] = '$$' + input() + '$$'

  dist = [[-1]*(w+4) for _ in range(h+4)]
  dist[ch + 1][cw + 1] = 0
  q = deque()
  q.append((ch+1, cw+1))
  while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    flag = [False, False, False, False]
    for i in range(4):
      nx = x + vx[i]
      ny = y + vy[i]
      if s[nx][ny] == '$': 
        flag[i] = True
        continue # 壁なら通れないね！
      if s[nx][ny] == '#':
        flag[i] = True
        continue
      if dist[nx][ny] != -1:
        if dist[nnx][nny] > dist[x][y]:
          dist[nnx][nny] = dist[x][y]
        flag[i] = True
        continue # もう最短距離がわかってるなら飛ばす
      dist[nx][ny] = dist[x][y]
      q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく
    if not False in flag: # もし4つのflagがTrueの時5×5以内に飛べるか探す
      vvx = [-2,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2]
      vvy = [0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2,1,1,1,1,2,2,2,2,2]
      for i in range(20):
        nnx = x + vvx[i]
        nny = y + vvy[i]
        if s[nnx][nny] == '$': 
          continue # 壁なら通れないね！
        if s[nnx][nny] == '#':
          continue
        if dist[nnx][nny] != -1:
          if dist[nnx][nny] > dist[x][y] + 1:
            dist[nnx][nny] = dist[x][y] + 1
          continue # もう最短距離がわかってるなら飛ばす
        dist[nnx][nny] = dist[x][y] + 1
        q.append((nnx, nny))
  
  print(dist[dh+1][dw+1])

if __name__ == '__main__':
  main()

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(1):
                    for dx in range(1):
                        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()