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=[ 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:
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):
    if(v[i][j]==1):
        return
    v[i][j]=1
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(k1==k2):
                continue
            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:
# 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
    return 0

def main():
    print(solve())


if __name__ == "__main__":
    main()

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]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
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 numpy as np

h,w = map(int,input().split())
sh,sw = map(int,input().split())
sh -= 1
sw -= 1
gh,gw = map(int,input().split())
gh -= 1
gw -= 1
s = np.array([list(input()) for _ in range(h)])

def dfs(nh,nw,c):
    s[nh][nw] = c
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if (-1 < nh+dy < h) and (-1 < nw+dx < w):
            if s[nh+dy][nw+dx] == ".":
                dfs(nh+dy,nw+dx,c)
            elif s[nh+dy][nw+dx] == "#":
                pass
            elif int(s[nh+dy][nw+dx]) > c:
                dfs(nh+dy,nw+dx,c)

    for dy,dx in [[1,1],[-1,-1],[-1,1],[1,-1]]:
        if (-1 < nh+dy < h) and (-1 < nw+dx < w):
            if s[nh+dy][nw+dx] == ".":
                dfs(nh+dy,nw+dx,c+1)
            elif s[nh+dy][nw+dx] == "#":
                pass
            elif int(s[nh+dy][nw+dx]) > c+1:
                dfs(nh+dy,nw+dx,c+1)
    
    for dy,dx in [[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2],[2,-1],[2,0],[2,1],[2,2],[1,2],[0,2],[-1,2],[-2,2],[-2,1],[-2,0],[-2,-1]]:
        if (-1 < nh+dy < h) and (-1 < nw+dx < w):
            if s[nh+dy][nw+dx] == ".":
                dfs(nh+dy,nw+dx,c+1)
            elif s[nh+dy][nw+dx] == "#":
                pass
            elif int(s[nh+dy][nw+dx]) > c+1:
                dfs(nh+dy,nw+dx,c+1)


dfs(sh,sw,0)

if s[gh][gw] == ".":
    print(-1)
else:
    print(s[gh][gw])

Submission status: Runtime Error

Solution code:
import queue
import sys
input = sys.stdin.readline
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 _ in range(h)]
p = [False for _ in range(w*h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
q = queue.Queue()
q.put((ch,cw))
l = [(ch,cw)]
la = l.append
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[h*j+k] = True
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[h*(j+hi)+k+wi] == False:
            q.put((j+hi,k+wi))
            la((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi 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  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[h*(j+hi)+k+wi] == False:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[h*(j+hi)+k+wi] = True
  if q.empty():
    print(-1)
    exit()
  l = nl
  la = l.append
  i += 1

Submission status: Runtime Error

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

import collections
import itertools
import bisect

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())
    sys.setrecursionlimit(10000)

    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:
H, W = [ int(v) for v in input().split(" ") ]
Ch, Cw = [ int(v)-1 for v in input().split(" ") ]
Gh, Gw = [ int(v)-1 for v in input().split(" ") ]
S = []
for i in range(H):
  S.extend(input().split(" "))

total = 0
while True:
  #print(Ch,Cw)
  if Ch == Gh and Cw == Gw:
    break
  elif Ch < Gh and S[Ch+1][Cw] == ".":
    Ch += 1
  elif Ch > Gh and S[Ch-1][Cw] == ".":
    Ch -= 1
  elif Cw < Gw and S[Ch][Cw+1] == ".":
    Cw += 1
  elif Cw > Gw and S[Ch][Cw-1] == ".":
    Cw -= 1 
  else:
    #print("(∩^o^)⊃━☆")
    h = Gh - Ch
    w = Gw - Cw
    total += 1
    jump_flag = False

    if abs(h) + abs(w) <= 5:
      break
    elif abs(h) > 5:
      for i in reversed(range(5)):
        for j in range(5-i):
          if c[i][j] == ".":
            Ch += i
            Cw += j
            jump_flag = True
            break
        if jump_flag: break
    elif abs(w) > 5:
      for i in reversed(range(5)):
        for j in range(5-i):
          if c[j][i] == ".":
            Ch += j
            Cw += i
            jump_flag = True
            break
        if jump_flag: break
    else:
      total = -1
      break

print(total)

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
    return 0

def main():
    print(solve())


if __name__ == "__main__":
    main()

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]
 
if N==1 and M==1:
    if S[0,0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
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:
h, w = list(map(int, input().split()))
cx, cy = list(map(lambda c: int(c) - 1, input().split()))
dx, dy = list(map(lambda c: int(c) - 1, input().split()))
m = []

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

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 and 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):
            if abs(i) + abs(j) <= 1: continue
            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
inf=float("inf")

import numpy as np
def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-3),min(h,x+3)):
            for Y in range(max(0,y-3),min(w,y+3)):
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    if color[X][Y]=="white":
                        queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000)

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
# 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()