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:
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())+['#']*8)

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

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)

#for x in matrix:
#	print(*x)

if matrix[hend-1][wend-1] == '.':
	print(-1)
else:
	print(matrix[hend-1][wend-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = set()
BFS_now.add((Ch-1, Cw-1))
BFS_search = set()
BFS_search.add((Ch-1, Cw-1))
ij = [(-1,0),(0,-1),(0,1),(1,0)]

while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = set()
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.add((h+i,w+j))
          BFS_now.add((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = set()
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.add((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

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

Submission status: Runtime Error

Solution code:
import queue

def bfs(x, y):
    if M[x][y] == c:
        return False
    else:
        M[x][y] = c
    q = queue.Queue()
    q.put([x,y])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        if nowx ==  D1 - 1 and nowy == D2 -1:
            return True
        if 0 < nowy and m[nowx][nowy -1] == '.' and M[nowx][nowy -1] == -1:
            M[nowx][nowy -1] = c
            q.put([nowx,nowy-1])
        if H-1 > nowy and m[nowx][nowy +1] == '.' and M[nowx][nowy +1] == -1:
            M[nowx][nowy +1] = c
            q.put([nowx,nowy+1])
        if 0 < nowx and m[nowx - 1][nowy] == '.'and M[nowx - 1][nowy] == -1:
            M[nowx - 1][nowy] = c
            q.put([nowx - 1,nowy])
        if W - 1 > nowx and m[nowx + 1][nowy] == '.'and M[nowx + 1][nowy] == -1:
            M[nowx + 1][nowy] = c
            q.put([nowx + 1,nowy])
    return False



def jump():
    for i in range (H):
        for j in range (W):
            if M[i][j] == c:
                for k in range(max(0,i-2),min(H,i+3)):
                    for l in range(max(0,j-2),min(W,j+3)):
                        if M[k][l] == -1 and m[k][l] == '.':
                            Q.put([k,l])




H,W = map(int,input().split())
C1,C2 =map(int,input().split())
D1,D2 = map(int,input().split())

m = []
for i in range (H):
    m.append(list(input()))



M = [[-1 for i in range (W)] for j in range (H)]
c = 0
Q = queue.Queue()

Q.put([C1-1,C2-1])
flag = False
f2 = False
while True:
    if Q.empty():
        print(-1)
        f2 = True
        break
    while not Q.empty():
        x,y = Q.get()
        if bfs(x,y) == True:
            flag = True
            break
    if flag == True:
        break
    else:
        jump()
        c += 1

if not f2:
    print(c)

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())+['#']*8)

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

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)

for x in matrix:
	print(*x)

if matrix[hend-1][wend-1] == '.':
	print(-1)
else:
	print(matrix[hend-1][wend-1])

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

already=0
def calc(update_list,value):
  for h,w in update_list:
    if maze[h][w]!=-1 and maze[h][w]<value:continue
    u=update(maze,h,w,value,[])
    calc(u,value+1)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from typing import List
import sys


def dump_s(s: list) -> None:
    print("dump_s:")
    for h_index in range(1, len(s)):
        print(''.join(s[h_index]))


def fill(h: int, w: int, c_h: int, c_w: int, s: list, fill_char: str = 'o') -> list:
    ret = list()
    if s[c_h][c_w] == '.':
        s[c_h][c_w] = fill_char
        ret.append((c_h, c_w,))
    if c_h > 1 and s[c_h - 1][c_w] == '.':
        ret.extend(fill(h, w, c_h - 1, c_w, s, fill_char))
    if c_h < h and s[c_h + 1][c_w] == '.':
        ret.extend(fill(h, w, c_h + 1, c_w, s, fill_char))
    if c_w > 1 and s[c_h][c_w - 1] == '.':
        ret.extend(fill(h, w, c_h, c_w - 1, s, fill_char))
    if c_w < w and s[c_h][c_w + 1] == '.':
        ret.extend(fill(h, w, c_h, c_w + 1, s, fill_char))
    return ret


def f(h: int, w: int, c_h: int, c_w: int, d_h: int, d_w: int, s: list) -> int:
    # move a
    filled = fill(h, w, c_h, c_w, s)
    for t in filled:
        if t[0] == d_h and t[1] == d_w:
            return 0

    # move b
    wp_candidate_dic = dict()
    for t in filled:
        h0 = t[0] - 2 if t[0] - 2 >= 1 else 1
        w0 = t[1] - 2 if t[1] - 2 >= 1 else 1
        h1 = t[0] + 2 if t[0] + 2 <= h else h
        w1 = t[1] + 2 if t[1] + 2 <= w else w
        for h_index in range(h0, h1+1):
            for w_index in range(w0, w1+1):
                wp = (h_index, w_index)
                if wp not in wp_candidate_dic and s[h_index][w_index] == '.':
                    wp_candidate_dic[wp] = True

    for t in wp_candidate_dic:
        filled_x = fill(h, w, t[0], t[1], s, 'x')
        for pt in filled_x:
            if pt[0] == c_h and pt[1] == c_w:
                return 1
        for pt in filled_x:
            s[pt[0]][pt[1]] = '.'

    for t in wp_candidate_dic:
        ret = f(h, w, t[0], t[1], d_h, d_w, s)
        if ret >= 0:
            return ret + 1

    return -1


if __name__ == '__main__':
    h, w = list(map(lambda x: int(x), input().split()))
    c_h, c_w = list(map(lambda x: int(x), input().split()))
    d_h, d_w = list(map(lambda x: int(x), input().split()))
    s: List[list] = list()
    s.append(list())
    for h_index in range(1, h+1):
        rec = list(input())
        rec.insert(0, '')
        s.append(rec)
    print(f(h, w, c_h, c_w, d_h, d_w, s))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  return h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1

warp = 0
BFS_now = set()
BFS_now.add((Ch-1, Cw-1))
BFS_search = set()
BFS_search.add((Ch-1, Cw-1))
ij = [(-1,0),(0,-1),(0,1),(1,0)]

while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = set()
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.add((h+i,w+j))
          BFS_now.add((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = set()
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.add((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-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):
    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 input().split()]
x1,y1=[int(i)-1 for i in input().split()]
x2,y2=[int(i)-1 for i in input().split()]
dp=[[10**9 for i in range(m)]for j in range(n)]
a=[[i for i in 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:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
  int h,w,sx,sy,gx,gy;
  cin >> h >> w;
  cin >> sx >> sy;
  cin >> gx >> gy;
  sx--;
  sy--;
  gx--;
  gy--;
  vector<string> S(h);
  for (int i = 0; i < h; i++)
  {
    cin >> S[i];
  }
  

  vector<vector<int>> A = {{-1,0},{1,0},{0,-1},{0,1}};
  vector<vector<int>> B;
  for (int i = -2; i < 3; i++)
  {
    for (int j = -2; j < 3; j++)
    {
      if (i!=0 && j!=0)
      {
        B.push_back({i,j});
      }
    }
    
  }
  int n = h*w;
  vector<vector<vector<int>>> M(n);
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      if (S[i][j] == '.')
      {
        for (int k = 0; k < A.size(); k++)
        {
          int ai = i + A[k][0];
          int aj = j + A[k][1];
          if (0 <= ai && (ai < h && (0 <= aj && (aj < w && S[ai][aj] == '.'))))
          {
            M[i*w+j].push_back({ai*w+aj, 0});
          }
        }
        for (int k = 0; k < B.size(); k++)
        {
          int ai = i + B[k][0];
          int aj = j + B[k][1];
          if (0 <= ai && (ai < h && (0 <= aj && (aj < w && S[ai][aj] == '.'))))
          {
            M[i*w+j].push_back({ai*w+aj, 1});
          }
        }
        
      }
    }
  }

  vector<int>  D(n, pow(10,9));
  D[sx*w+sy] = 0;
  vector<int>  V(n, 0);
  priority_queue<vector<int>> Q;
  for (int i = 0; i < n; i++)
  {
    Q.push({-D[i], i});
  }

  int le,u,du,luv,alt,v;
  vector<int> q;
  le = Q.size();
  while (le > 0)
  {
    q = Q.top();
    Q.pop();
    u = q[1];
    du = -q[0];
    if (V[u] == 0)
    {
      V[u] = 1;
      le -= 1;
      for (int i = 0; i < M[u].size(); i++)
      {
        v = M[u][i][0];
        luv = M[u][i][1];
        if (V[v] == 0)
        {
          alt = du + luv;
          if (D[v] > alt)
          {
            D[v] = alt;
            Q.push({-alt, v});
          }
        }
      }
      
    }
  }




  int ans = D[gx*w+gy];
  if (ans > pow(10, 6) + 5)
  {
    ans = -1;
  }
  // for (int i = 0; i < n; i++)
  // {
  //   cout << i/w << " " << i%w << " " << D[i] << endl;
  // }
  


  cout << ans << endl;
}

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 = [None]*(H+4)
S[0] = S[1] = S[H+2] = S[H+3] = ["#"]*(W+4)
for i in range(2, H+2):
    S[i] = ["#"] + ["#"] + list(input()) + ["#"] + ["#"]

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

del_h = Dh - Ch
del_w = Dw - Cw

ans = int(10e9)
# print("\n".join(map(str, S)))

def warp(i, j, nxt):
    for h in range(i-2, i+3):
        for w in range(j-2, j+3):
            # print(h, w, i, j)
            # print(S[h][w])
            if S[h][w] == ".":
                nxt.append([h, w, 1])
    
    return 

def dfs(i, j, S, cnt):
    if i == Dh and j == Dw:
        global ans
        ans = min(ans, cnt)
        return 

    S[i][j] = "#"
    nxt = list()
    if S[i][j-1] == ".":
        nxt.append([i, j-1, 0])
    if S[i][j+1] == ".":
        nxt.append([i, j+1, 0])
    if S[i-1][j+1] == ".":
        nxt.append([i-1, j, 0])
    if S[i+1][j] == ".":
        nxt.append([i+1, j, 0])
    warp(i, j, nxt)
    
    for point in nxt:
        cnt += point[2]
        dfs(point[0], point[1], S, cnt)
    
    # S[i][j] = "."

dfs(Ch, Cw, S, 0)
if ans == int(10e9):
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
ch, dh = map(int, input().split())
cw, dw = map(int, input().split())

S = []
for _ in range(H):
    s = list(map(str, input()))
    S.append(s)


node = [[-1 for i in range(W)] for j in range(H)]
node[ch-1][cw-1] = 0


start = [[ch-1, cw-1]]

houkou = [[0, 1],[0, -1], [1, 0], [-1,0]]

ans = 0

while len(start) != 0:
        road = start.pop(0)
        h = road[0]
        w = road[1]
        for i in houkou:

            if 0 <= h+i[0] and h+i[0] < H:
                if 0 <= w+i[1] and w+i[1] < W:
                    if S[h+i[0]][w+i[1]] == '.':
                        node[h+i[0]][w+i[1]] = node[h][w]
                        start.append([h+i[0], w+i[1]])

        if node[dh-1][dw-1] == 0:
            break

l = [[ch-1, cw-1]]

if node[dh-1][dw-1] != 0:
    while len(l)!=0:
        ll = l.pop(0)
        h,w = ll[0], ll[1]
        if S[h][w] == '.':
                for x in [-2, -1, 0, 1, 2]:
                    for y in [-2, -1, 0, 1, 2]:
                        if 0 <= h+x < H:
                            if 0 <= w+y < W:
                                if S[h+x][w+y] == '.' :
                                    if (node[h+x][w+y] > node[h][w]) or (node[h+x][w+y] == -1):
                                        if [x, y] in [[1,0],[-1,0],[0,1],[0,-1]]:
                                            node[h+x][w+y] = node[h][w]
                                            l.append([h+x,w+y])
                                        else:
                                            node[h+x][w+y] = node[h][w] + 1
                                            l.append([h+x,w+y])



print(node[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())
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(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[ny][nx]:
                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]:
                mp[ny][nx] = min(mp[ny][nx], mp[y][x]+1)

    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])

'''
for i in range(h):
    print(mp[i])
'''

Submission status: Runtime Error

Solution code:
from collections import defaultdict
H,W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
M = list()
A = defaultdict(list)
for i in range(H):
  tmp = input()
  map_w = list()
  for i in range(W):
    num = 0 if tmp[i] == '.' else -1
    map_w.append(num)
  M.append(map_w)

color = 1
def paint(c, i, j):
  M[j][i] = c
  A[color].append([i,j])
  if j < H - 1 and M[i][j + 1] == 0:
    paint(c, i , j + 1)
  if j > 0 and M[i][j - 1] == 0:
    paint(c, i , j - 1)
  if i < W - 1 and M[j][i + 1] == 0:
    paint(c, i + 1, j )
  if i > 0 and M[j][i - 1] == 0:
    paint(c, i - 1, j )

for j in range(H):
  for i in range(W):
    if M[j][i] == 0:      
      paint(color, i, j)
      color += 1




if M[Cw][Ch] == M[Dw][Dh]:
  ret = 0
else:
  SC = M[Cw][Ch]
  FD = M[Dw][Dh]
  
  ret = list()

  def findnext(c, l):
    for p in A[c]:
      i, j  = p[0], p[1] 
      xl, xr = max(i - 2, 0), min(i + 3, W )
      yt, yb = max(j - 2, 0), min(j + 3, H )
      ret_ = set()
      for j in range(yt, yb):
          tmp_ = M[j][xl:xr]
          tmp_ = set([a for a in tmp_ if a != -1 and a != c])
          for k in tmp_:
            ret_.add(k)
      if FD in ret_:
        l_ = l.copy()
        l_.append(c)
        ret.append(len(l_))
      elif len(ret_) > 0:
        next_ = [a for a in ret_ if a not in l]
        for n_ in next_:
          l_ = l.copy()
          l_.append(c)
          findnext(n_, l_ ) 
  findnext(SC, [])
if len(ret) > 0:
  print(min(ret))
else:
  print(-1)

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] = str(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 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 (i, j) == (Dh, Dw):
    return 0
  if f[i][j]:
    return None
  f[i][j] = True
  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:
def C_BFS2(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs2(maze, row, column, sy, sx, gy, gx):
        tmp = [[2,2],[2,1],[2,0],[2,-1],[2,-2],\
       [1,2],[1,-2],[0,2],[0,-2],\
       [-1,2],[-1,-2],\
       [-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                 # ゴール座標と一致するなら
                break
            for i in range(16):
                nx = x + tmp[i][0]
                ny = y + tmp[i][1]
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    if dist[ny][nx] > dist[y][x]:
                        dist[ny][nx] = dist[y][x]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs2(maze, R, C, sy, sx, gy, gx)
    return ans
  
  def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x]
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]
import sys
# スタート地点は全て試す
dist_ans = 0
dist_tmp = C_BFS(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
INF = float('inf')
if dist_tmp == 0:
    print(0)
    sys.exit()
else:
    dist_ans = 0
    dist_tmp = C_BFS2(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
    INF = float('inf')
    if dist_tmp == INF:
        print(-1)
    else:
        print(dist_tmp)

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 Ch < H-1 and S[Ch+1][Cw] == ".":
    Ch += 1
  elif Ch > Gh and Ch > 0 and S[Ch-1][Cw] == ".":
    Ch -= 1
  elif Cw < Gw and Cw < W-1 and S[Ch][Cw+1] == ".":
    Cw += 1
  elif Cw > Gw and Cw > 0 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:
def solve(s_flag,h,w,ch,cw,jump_cnt):
    # print(ch,cw,jump_cnt)
    # print(s_flag)
    if s_flag[ch][cw]==-1:
        return [(ch,cw,jump_cnt)]
    s_flag[ch][cw]=1 ## 1:visited
    for d_ch,d_cw in [(1,0),(0,1),(0,-1),(-1,0)]:
        if ch+d_ch<0 or h-1<ch+d_ch:
            continue
        if cw+d_cw<0 or w-1<cw+d_cw:
            continue
        if s_flag[ch+d_ch][cw+d_cw]==2: ## 2:wall
            jump=[(d_ch*2,d_cw*2)]
            for tmp in range(1,3):
                jump.append((d_ch*2+d_cw*tmp,d_cw*2+d_ch*tmp))
                jump.append((d_ch*2-d_cw*tmp,d_cw*2-d_ch*tmp))
            for jump_ch,jump_cw in jump:
                if ch+jump_ch<0 or h-1<ch+jump_ch:
                    continue
                if cw+jump_cw<0 or w-1<cw+jump_cw:
                    continue
                if s_flag[ch+jump_ch][cw+jump_cw]<=0:
                    route=solve(s_flag,h,w,ch+jump_ch,cw+jump_cw,jump_cnt+1)
                    if route:
                        return [(ch,cw,jump_cnt)]+route
        elif s_flag[ch+d_ch][cw+d_cw]<=0: ## 0:road -1:goal
            route=solve(s_flag,h,w,ch+d_ch,cw+d_cw,jump_cnt)
            if route:
                return [(ch,cw,jump_cnt)]+route


def main():
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    s=[input() for i in range(h)]
    ## .=0 #=2 visited=1 goal=-1
    s_flag=[[0 if s[i][j]=='.' else 2 for j in range(w)] for i in range(h)]
    s_flag[ch-1][cw-1]=1
    s_flag[dh-1][dw-1]=-1
    ans=solve(s_flag,h,w,ch-1,cw-1,0)
    if not ans:
        ans=-1
    else:
        ans=ans[-1][2]
    return ans

if __name__=='__main__':
    ans=main()
    print(ans)