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 sys
sys.setrecursionlimit(4000)
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())
li = []
for i in range(h):
    li.append(list(input()))
a = li[ch-1][cw-1]
b = li[dh-1][dw-1]
if [cw]==w and [ch]==h:
    if li[ch-1-1]=="#" and li[cw-2]=="#" :
        print(-1)
elif [cw]==w:
    if li[ch-1-1]=="#" and li[ch]=="#" and li[cw-2]=="#" :
        print(-1)
elif [ch]==h:
    if li[ch-1-1]=="#"  and li[cw-2]=="#" and li[cw]=="#":
        print(-1)
else :
 if ch-1 < dh-1:
    for i in range(w):
       if li[ch+i-1][cw-1] == ".":
           a = li[ch+i-1][cw-1]
           p = ch + i -1
           if p == dh:

               break
       else :
           p = ch-1
           break
 else:
    for i in range(w):
     if li[ch-i-1][cw-1]==".":
        a = li[ch-i-1][cw-1]=="."
        p = ch - i -1
        if p == dh:
            break
     else :
         p=ch-1
         break
 if cw-1 < dw-1 :
    for i in range(h):
     if li[p][cw+i-1]==".":
         a = li[p][cw+i-1]
         q = cw +i-1
         if q == dw:
             break
     else :
         q = cw-1
         break
 else :
    for i in range(h):
     if li[p][cw-i-1]==".":
         a = li[p][cw-1-1]
         q = cw-1-1
         if q ==dw :
             break
     else :
         q = cw-1
 now = li[p][q]
 if p == dh and q == dw:
    print(0)
    exit()
 ans =0

 for an in range(10**3):
    if abs(p-dh) <=5*an and abs(q-dw) <=5*an :
        ans += 1
        print(ans)
        break
    else :
        if p < dh:
            p = p + 5
        else :
            p = p-5
        if q < dw:
            q = q+5
        else :
            q = q-5

Submission status: Runtime Error

Solution code:
h,w=input().split()
x,y=input().split()
x_target,y_target=input().split()
h=int(h)
w=int(w)
x=int(x)-1
y=int(y)-1
x_target=int(x_target)-1
y_target=int(y_target)-1
square=[]
for i in range(h):
    square.append(list(input()))
print(square)
wizard_loc=square[x][y]
destination=square[x_target][y_target]
print(wizard_loc)
print(destination)
if square[x-2:x+3][y-2:y+3]|square[x_target-2:x_target+3][y_target-2:y_target+3]:
    print(1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    s = [['#'] + list(input()) + ['#'] for _ in range(h)]
    wall = ['#'] * (w + 2)
    s.insert(0, wall)
    s.append(wall)

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    group = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    gd = defaultdict(list)

    def dfs(i, j, g):
        if visited[i][j]:
            return
        visited[i][j] = True
        group[i][j] = g
        gd[g].append((i, j))
        for p, q in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if s[i + p][j + q] == '#':
                continue
            dfs(i + p, j + q, g)

    g = 1
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == '#':
                continue
            dfs(i, j, g)
            g += 1

    gstart = group[ch][cw]
    ggoal = group[dh][dw]

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def search(i, j, gfrom, step):
        visited[i][j] = True
        gij = group[i][j]
        if gij != gfrom:
            step += 1
        if gij == ggoal:
            return step
        for p in range(-2, 3):
            for q in range(-2, 3):
                if not 1 <= i + p <= h + 1:
                    continue
                if not 1 <= j + q <= w + 1:
                    continue
                if s[i + p][j + q] == '#':
                    continue
                if visited[i + p][j + q]:
                    continue
                return search(i + p, j + q, gij, step)

    g = gstart
    gs = gd[g]
    ans = float('Inf')
    if gstart == ggoal:
        print(0)
        return
    for (i, j) in gs:
        res = search(i, j, 1, 0)
        if res is not None:
            ans = min(ans, res)

    print(-1 if ans == float('Inf') else ans)


if __name__ == '__main__':
    main()

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 = [input().split() for l in range(h)]

def search(x, y, ans ,warp_sw):
    if s[ch][cw] == s[dh][dw]:
        return ans
    
    s[ch][cw] = "D"
    
    if s[ch - 1][cw] == ".":
        search(x - 1, y, ans,warp_sw)
    if s[ch + 1][cw] == ".":
        search(x + 1, y, ans,warp_sw)
    if s[ch][cw - 1] == ".":
        search(x, y - 1, ans,warp_sw)
    if s[ch][cw + 1] == ".":
        search(x, y + 1, ans,warp_sw)
    
    s[ch][cw] = "."
    
    if s[ch + 2][cw - 1] == ".":
        search(x + 2, y - 1, ans + 1,warp_sw)
    if s[ch + 2][cw] == ".":
        search(x + 2, y, ans + 1,warp_sw)
    if s[ch + 2][cw + 1] == ".":
        search(x + 2, y + 1, ans + 1,warp_sw)
    if s[ch - 2][cw - 1] == ".":
       search(x - 2, y - 1, ans + 1,warp_sw) 
    if s[ch - 2][cw] == ".":
       search(x - 2, y, ans + 1,warp_sw) 
    if s[ch - 2][cw + 1] == ".":
       search(x - 2, y + 1, ans + 1,warp_sw) 
    if s[ch - 1][cw - 2] == ".":
       search(x - 1, y - 2, ans + 1,warp_sw)
    if s[ch][cw - 2] == ".":
       search(x, y - 2, ans + 1,warp_sw)
    if s[ch + 1][cw - 2] == ".":
       search(x + 1, y - 2, ans + 1,warp_sw)
    if s[ch - 1][cw + 2] == ".":
       search(x - 1, y + 2, ans + 1,warp_sw)
    if s[ch][cw + 2] == ".":
       search(x, y + 2, ans + 1,warp_sw)
    if s[ch + 1][cw + 2] == ".":
       search(x + 1, y + 2, ans + 1,warp_sw)

    return -1

search(ch, cw, 0, 0)

Submission status: Runtime Error

Solution code:
# [int(i) for i in input().split(' ')]
h, w = [int(i) for i in input().split(' ')]
startX, startY = [int(i) for i in input().split(' ')]
goalX, goalY = [int(i) for i in input().split(' ')]

s = list()
for i in range(h):
    s.append([-1 if i == '#' else 0 for i in input()])
able = False

def exploreWalk(x, y, CN, target):
    s[x][y] = CN
    if x-1 >= 0:
        if s[x-1][y] == target:
            exploreWalk(x-1, y, CN, target)
    if y-1 >= 0:
        if s[x][y-1] == target:
            exploreWalk(x, y-1, CN, target)
    if x+1 < h:
        if s[x+1][y] == target:
            exploreWalk(x+1, y, CN, target)
    if y+1 < w:
        if s[x][y+1] == target:
            exploreWalk(x, y+1, CN, target)

def exploreWarp(x, y, CN, tmp):
    for i in range(max(0, x-2),min(h-1, x+2)+1):
        for j in range(max(0, y-2), min(w-1, y+2)+1):
            if s[i][j] > CN+1 or s[i][j] == 0:
                explore(i, j, CN+1, s[i][j])
    tmp[x][y] = True
    if x-1 >= 0:
        if s[x-1][y] == CN and tmp[x-1][y] == False:
            exploreWarp(x-1, y, CN, tmp)
    if y-1 >= 0:
        if s[x][y-1] == CN and tmp[x][y-1] == False:
            exploreWarp(x, y-1, CN, tmp)
    if x+1 < h:
        if s[x+1][y] == CN and tmp[x+1][y] == False:
            exploreWarp(x+1, y, CN, tmp)
    if y+1 < h:
        if s[x][y+1] == CN and tmp[x][y+1] == False:
            exploreWarp(x, y+1, CN, tmp)

def explore(x, y, currentNum, now):
    exploreWalk(x, y, currentNum, now)
    exploreWarp(x, y, currentNum, [[False] * len(s[0]) for i in range(len(s))])
    
explore(startX-1, startY-1, 1, 0)
ret = s[goalX-1][goalY-1]-1

print(ret)

Submission status: Runtime Error

Solution code:
def myfunc(h, w, c):
    if 0<=h and h<H+2 and 0<=w and w<W+2 and T[h][w] == '.':
        T[h][w] = c
        global warp
        warp = True
        for i in [(0,1), (0,-1), (1,0), (-1,0)]:
            myfunc(h+i[0], w+i[1], c)

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W*2))
S.append('#'*(W*2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
myfunc(CH, CW, 0)
warp = True
while T[DH][DW] == '.' and warp:
    warp = False
    for i in range(H+2):
        for j in range(W+2):
            if T[i][j] != '.' and T[i][j] != '#':
                for k in range(-2, 3):
                    for l in range(-2, 3):
                        myfunc(i+k, j+l, T[i][j]+1)
if warp == False:
    print(-1)
else:
    print(T[DH][DW])

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[goalx][goaly]
 
            
print(dfs(starty,startx))

Submission status: Runtime Error

Solution code:
import queue

dx = [-1,0,1,0]
dy = [0,-1,0,1]

def bfs(ch,cw):
    q = [queue.Queue() for _ in range(2000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
            break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
f=lambda x:int(x)-1
c1,c2=map(f,input().split())
d1,d2=map(f,input().split())
l=[input() for _ in range(h)]

queue=[]
queue.append([c1,c2])
visit=[[0]*w for _ in range(h)]

wapcnt=0
nokori=h+w+2
while True:
  while len(queue)>0:
    x,y=queue.pop(0)
    if x==d1 and y==d2:
      print(wapcnt)
      exit()
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      if 0<=x+i<=h-1 and 0<=y+j<=w-1:
        if visit[x+i][y+j]==0 and l[x+i][y+j]=='.':
          visit[x+i][y+j]=1
          queue.append([x+i,y+j])
          nokori=min(nokori,abs(x+i-d1)+abs(y+j-d2))
  if nokori<=4:
    wapcnt+=1
    print(wapcnt)
    exit()
  m=4
  ll=[]
  for p in range(-2,3):
    for q in range(-2,3):
      if 0<=x+p<h and 0<=y+q<w:
        if l[x+p][y+q]=='.' and visit[x+p][y+q]==0:
          if not p==q==0:
            m=min(m,abs(x+p-d1)+abs(y+q-d2))
            ll.append([p,q,abs(x+p-d1)+abs(y+q-d2)])
  if ll==[]:
    print(-1)
    exit()
  nokori-=m
  for lll in ll:
    if lll[2]==m:
      a=lll[0]
      b=lll[1]
  queue.append([x+a,y+b])
  wapcnt+=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):
        if S[h][w]=="#":
            continue
        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:
import sys

sys.setrecursionlimit(10000)

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,l):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=l
  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,l)
      
  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

def calc(update_list):
  for h,w in update_list:
    u=update(maze,h,w,maze[h][w],[])
    calc(u)

update_list=update(maze,Ch-1,Cw-1,0,[])
calc(update_list)

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9) 
H, W = map(int, input().split())
Cl = list(map(int, input().split()))
Dl = list(map(int, input().split()))
H -= 1
W -= 1
C = (Cl[0]-1, Cl[1]-1)
D = (Dl[0]-1, Dl[1]-1)
S = list()
for _ in range(H+1):
  S.append(list(input()))
  
ans = defaultdict(lambda: float("inf"))
foot = [(1, 0), (0, 1), (-1, 0), (0, -1)]
magic = [\
         (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
         (-1, -2), (-1, -1), (-2, 0), (-2, 1), (-2, 2), \
         ( 0, -2), ( 0, -1), ( 0, 0), ( 0, 1), ( 0, 2), \
         ( 1, -2), ( 1, -1), ( 1, 0), ( 1, 1), ( 1, 2), \
         ( 2, -2), ( 2, -1), ( 2, 0), ( 2, 1), ( 2, 2), \
        ]
def dfs(i, y, x):
  global H, W, D, S, ans, foot
  ans[(y, x)] = min(ans[(y, x)], i)
  if (y, x) == D:
    return
  for dx, dy in foot:
    nextx = x+dx
    nexty = y+dy
    if (0<=nextx<=W) and (0<=nexty<=H) and (S[nexty][nextx]==".") and ((ans[(nexty, nextx)]<i) or (ans[(nexty, nextx)]==float("inf"))):
      dfs(i, nexty, nextx)
  for dx, dy in magic:
    nextx = x+dx
    nexty = y+dy 
  if (0<=nextx<=W) and (0<=nexty<=H) and (S[nexty][nextx]==".") and ((ans[(nexty, nextx)]<i) or (ans[(nexty, nextx)]==float("inf"))):
    dfs(i+1, nexty, nextx)

dfs(0, C[0], C[1])
if ans[D[0], D[1]] == float("inf"):
  print(-1)
else:
  print(ans[D[0], D[1]])

Submission status: Runtime Error

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

H = 0
W = 0
table = None


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

    if(type(table[h][w]) is int and table[h][w] < cnt):
        return

    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, 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, 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, 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, cnt+1)


def main(input, print):
    global H, W, table
    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, 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:
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)
  if not (0 <= i < H and 0 <= j < W):
    return None
  if f[i][j]:
    return None
  f[i][j] = True
  if (i, j) == (Dh, Dw):
    return 0
  if S[i][j] == '#':
    return None

  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):
      if (wi, wj) == (0, 0):
        continue
      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)

Submission status: Runtime Error

Solution code:
H,W=list(map(int,input().split()))
X_s,Y_s=list(map(int,input().split()))
X_g,Y_g=list(map(int,input().split()))
l=[list(input()) for _ in range(H)]
l_map=[[0]*W for _ in range(H)]
from collections import deque
def tansaku(X,Y,nu):
   sw=0
   que=deque([[X,Y]])
   after=deque([])
   while que:
      tmpX,tmpY=que.popleft()
      after.append([tmpX,tmpY])
      tmpX,tmpY=int(tmpX),int(tmpY)
      l_map[tmpY][tmpX]= nu
      if nu == 1 or nu-1 in sum(l_map[0 if tmpY-2<0 else tmpY-2:H if tmpY+2>H-1 else tmpY+2][0 if tmpX-2<0 else tmpX-2:W if tmpX+2>W-1 else tmpX+2],[]):
         sw=1
      if tmpX>0:
         if l[tmpY][tmpX-1] == "." and [tmpX-1,tmpY] not in after:
            que.append([tmpX-1,tmpY])
      if 0<tmpY:
         if l[tmpY-1][tmpX] == "." and [tmpX,tmpY-1] not in after:
            que.append([tmpX,tmpY-1])
      if tmpX<W-1:
         if l[tmpY][tmpX+1] == "." and [tmpX+1,tmpY] not in after:
            que.append([tmpX+1,tmpY])
      if tmpY<H-1:
         if l[tmpY+1][tmpX] == "." and [tmpX,tmpY+1] not in after:
            que.append([tmpX,tmpY+1])
   if sw==0:
      print("-1")
      exit()
nu_now=0
for i in range(H):
   for j in range(W):
      if l_map[i][j]==0 and l[i][j]==".":
         nu_now+=1
         tansaku(str(j),str(i),nu_now)
print(l_map[Y_g-1][X_g-1]-l_map[Y_s-1][X_s-1],l_map)

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]
count = 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]] == count:
                mapping[i][j] = count + 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)
    count += 1

print(mapping[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(abs(k1)==abs(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

sys.setrecursionlimit(5000)

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,l):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=l
  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,l)
      
  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

def calc(update_list):
  for h,w in update_list:
    u=update(maze,h,w,maze[h][w],[])
    calc(u)

update_list=update(maze,Ch-1,Cw-1,0,[])
calc(update_list)

print(maze[Dh-1][Dw-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, -1), (1, 1), (-1, 1), (1, -1)])
    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:
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,l):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=l
  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,l)
      
  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

def calc(update_list):
  for h,w in update_list:
    u=update(maze,h,w,maze[h][w],[])
    calc(u)

update_list=update(maze,Ch-1,Cw-1,0,[])
calc(update_list)

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