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:
n = list(map(int, input().split()))
wizard = list(map(int, input().split()))
wizard[0] = wizard[0]-1
wizard[1] = wizard[1]-1
goal = list(map(int, input().split()))
goal[0] = goal[0]-1
goal[1] = goal[1]-1
maze = []
for i in range(n[0]):
    maze.append(input())
print(wizard)
print(goal)
print(maze)
def moveA():
    while wizard[0] > goal[0]:
        if maze[wizard[0]-1][wizard[1]] != '#':
            wizard[0] -= 1
        else:
            pass
            
    while wizard[0] < goal[0]:
        if maze[wizard[0]+1][wizard[1]] != '#':
            wizard[0] += 1
        else:
            pass
            
    while wizard[1] > goal[1]:
        if maze[wizard[0]][wizard[1]-1] != '#':
            wizard[1] -= 1
        else:
            pass
            
    while wizard[1] < goal[1]:
        if maze[wizard[0]][wizard[1]+1] != '#':
            wizard[1] += 1
        else:
            pass
            
def moveB():
    if wizard[0] > goal[0]:
        if wizard[1] > goal[1]:
            for i in range(2):
                for p in range(2):
                    if wizard[0] - i >= 0 and wizard[0] - i< n[0]:
                        if wizard[1] - p >= 0 and wizard[1] - p < n[1]:
                            if maze[wizard[0] - i][wizard[1] - p] != '#':
                                result += 1
                                wizard[0] = wizard[0] - i
                                wizard[1] = wizard[1] - p
                                pass
    elif wizard[0] > goal[0]:
        if wizard[1] < goal[1]:
            for i in range(2):
                for p in range(2):
                    if wizard[0] - i >= 0 and wizard[0] - i< n[0]:
                        if wizard[1] + p >= 0 and wizard[1] + p < n[1]:
                            if maze[wizard[0] - i][wizard[1] + p] != '#':
                                result += 1
                                wizard[0] = wizard[0] - i
                                wizard[1] = wizard[1] + p
                                pass
    elif wizard[0] < goal[0]:
        if wizard[1] > goal[1]:
            for i in range(2):
                for p in range(2):
                    if wizard[0] + i >= 0 and wizard[0] + i< n[0]:
                        if wizard[1] - p >= 0 and wizard[1] - p < n[1]:
                            if maze[wizard[0] + i][wizard[1] - p] != '#':
                                result += 1
                                wizard[0] = wizard[0] + i
                                wizard[1] = wizard[1] - p
                                pass
    elif wizard[0] < goal[0]:
        if wizard[1] < goal[1]:
            for i in range(2):
                for p in range(2):
                    if wizard[0] + i >= 0 and wizard[0] + i< n[0]:
                        if wizard[1] + p >= 0 and wizard[1] + p < n[1]:
                            if maze[wizard[0] + i][wizard[1] + p] != '#':
                                result += 1
                                wizard[0] = wizard[0] + i
                                wizard[1] = wizard[1] + p
                                pass
    elif wizard[0] == goal[0]:
        if wizard[1] < goal[1]:
            for p in range(2):
                if wizard[1] + p >= 0 and wizard[1] + p < n[1]:
                    if maze[wizard[0]][wizard[1] + p] != '#':
                        result += 1
                        wizard[1] = wizard[1] + p
                        pass
    elif wizard[0] < goal[0]:
        if wizard[1] == goal[1]:
            for i in range(2):
                if wizard[0] + i >= 0 and wizard[0] + i< n[0]:
                    if maze[wizard[0] + i][wizard[1]] != '#':
                        result += 1
                        wizard[0] = wizard[0] + i
                        pass
    else:
        status = -1
    if status != -1:
        if wizard[0] == goal[0] and wizard[1] == goal[1]:
            status = 0
        else:
            status = 1
    



status = 1
while status ==  1:
    
    moveA()
    if wizard[0] > goal[0]:
        if wizard[1] > goal[1]:
            if maze[wizard[0]+1][wizard[1]] == '#':
                if maze[wizard[0]][wizard[1]+1] == '#':
                    
                    moveB()
    if wizard[0] > goal[0]:
        if wizard[1] < goal[1]:
            if maze[wizard[0]+1][wizard[1]] == '#':
                if maze[wizard[0]][wizard[1]-1] == '#':
                    
                    moveB()
    if wizard[0] < goal[0]:
        if wizard[1] > goal[1]:
            if maze[wizard[0]-1][wizard[1]] == '#':
                if maze[wizard[0]][wizard[1]+1] == '#':
                    
                    moveB()
    if wizard[0] < goal[0]:
        if wizard[1] < goal[1]:
            if maze[wizard[0]-1][wizard[1]] == '#':
                if maze[wizard[0]][wizard[1]-1] == '#':
                    
                    moveB()
    if wizard[0] == goal[0]:
        if wizard[1] < goal[1]:
            if maze[wizard[0]][wizard[1]+1] == '#':
                
                moveB()
    if wizard[0] < goal[0]:
        if wizard[1] == goal[1]:
            if maze[wizard[0]+1][wizard[1]] == '#':
                
                moveB()
    if wizard[0] == goal[0]:
        if wizard[1] == goal[1]:
            
            status = 0
if status == 0:
    print(result)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
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

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

cnt = 0
reached = [[False]*W for _ in range(H)]
def bfs(sh, sw):
    global cnt
    d = deque()
    #reached[Ch][Cw] = True
    d.append((sh, sw))
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            cnt += 1
                            bfs(i, j)


bfs(Ch, Cw)
print(-1)

Submission status: Runtime Error

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

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:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if x==dw-1 and y==dh-1:
      break
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h and maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):

        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        if i==0:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]+2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]+2])
              ans[y+dy[i]+2][x+dx[i]+j] = ans[y][x]+1
        elif i==2:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]-2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]-2])
              ans[y+dy[i]-2][x+dx[i]+j] = ans[y][x]+1
              
        elif i==1:
          for j in range(-2,3):
            if 0 <= x+dx[i]+2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]+2] = ans[y][x]+1
        else:
          for j in range(-2,3):
            if 0 <= x+dx[i]-2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+j-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]-2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]-2] = ans[y][x]+1


bfs(ans)
print(ans[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
def get_position(node):
    h = node//W + 1
    w = node%W
    if w == 0:
        w = W
    return (h,w)

H,W = list(map(int,input().split()))
C_h,C_w = list(map(int,input().split()))
D_h,D_w = list(map(int,input().split()))

N=H*W

#壁のノード
wall=[]
for h in range(H):
    for w_idx,w in enumerate(list(input())):
        if w == '#':
            wall.append(W*h+w_idx+1)
#道のノード        
path=[_ for _ in range(1,N+1) if _ not in wall]

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N):
    n=n+1
    if n not in wall:
        up = n-W
        if up > 0 and up not in wall:
            ad[n].append(up)
            
        down = n+W
        if down <= N and down not in wall:
            ad[n].append(down)
            
        left = n-1
        if n % W != 1 and left not in wall and left > 0:
            ad[n].append(left)
        
        right = n+1
        if n % W != 0 and right not in wall:
            ad[n].append(right)     

from collections import deque
    
color = {}
for n in range(N):
    color[n+1] = -1

depth = {}
for n in range(N):
    depth[n+1] = -1
    
group = {}
# for n in range(N):
#     group[n+1] = -1
    
group_= 0
for p in path:
    if color[p] != -1: 
        continue
    elif color[p] == -1: 
        start = p
        color[start] = 0
        que = deque([start])
        visit = deque([])
        group_+=1
        group[group_] = [start]

    depth[start] = 0
    while len(que) > 0:
        start = que[0]
#         print(start,que)
        for v in ad[start]:
#             print(v,color[v])
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1
                group[group_].append(v)
                
        color[start] = 1
        visit.append(que.popleft())

print(group_conect)

Submission status: Runtime Error

Solution code:
from queue import Queue

A = set()
Q = Queue()
H = W = 0
S = []
worps = set()


def main():
    global H, W, Dh, Dw, S
    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)]
    Q.put(tuple([Ch, Cw, 0]))

    try:
        while item := Q.get_nowait():
            loop(item)
    except BaseException:
        pass

    print(min(worps)) if worps else print(-1)


def loop(current):
    print(current)
    ci, cj, worp = current
    if (ci, cj) == (Dh, Dw):
        worps.add(worp)

    A.add((ci, cj))
    move1 = False
    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        ni = ci + di
        nj = cj + dj
        if 0 < ni and ni <= H and 0 < nj and nj <= W and \
                S[ni - 1][nj - 1] == '.' and (ni, nj) not in A:
            Q.put((ni, nj, worp))
            move1 = True
    if not move1:
        for di in range(-2, 3):
            for dj in range(-2, 3):
                if (di, dj) == (0, 0):
                    continue
                ni = ci + di
                nj = cj + dj
                if 0 < ni and ni <= H and 0 < nj and nj <= W and \
                        S[ni - 1][nj - 1] == '.' and (ni, nj) not in A:
                    Q.put((ni, nj, worp + 1))

    try:
        while item := Q.get_nowait():
            loop(item)
    except BaseException:
        pass


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    
    dfs([(x, y, d) for x, y, d in stack2 if dp[ny, nx] > d])

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.pop()
    qq.append((xx, yy, kaisuu))
    visited[xx][yy] = True
    ls = []
    while qq:
        x, y, kaisuu = qq.pop()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
            visited[x+1][y] = True
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
            visited[x-1][y] = True
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
            visited[x][y+1] = True
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
            visited[x][y-1] = True
    for u in ls:
        a, b, d = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, d+1))
print(-1)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())

maze = [ None for _ in range(h) ]
reachable = [ [ None for _ in range(w) ] for _ in range(h) ]

for hi in range(h):
    maze[hi] = input()

def warpable(y, x):
    next_travels = []

    for j in range(-2, 3):
        for i in range(-2, 3):
            wy = y + j if 0 <= (y + j) < h else y
            wx = x + i if 0 <= (x + i) < w else x

            if reachable[wy][wx] is None and maze[wy][wx] == '.':
                next_travels.append((wy, wx))

    return next_travels

def traveling(y, x, warp_count):
    if reachable[y][x] is None:
        reachable[y][x] = warp_count

    else:
        reachable[y][x] = warp_count if warp_count < reachable[y][x] else reachable[y][x]

    u = y - 1 if (y - 1) >= 0 else y
    d = y + 1 if (y + 1) <  h else y
    l = x - 1 if (x - 1) >= 0 else x
    r = x + 1 if (x + 1) <  w else x

    next_travels = []

    if reachable[u][x] is None and maze[u][x] == '.':
        next_travels.append((u, x))

    if reachable[d][x] is None and maze[d][x] == '.':
        next_travels.append((d, x))

    if reachable[y][l] is None and maze[y][l] == '.':
        next_travels.append((y, l))

    if reachable[y][r] is None and maze[y][r] == '.':
        next_travels.append((y, r))

    if len(next_travels) == 0:
        warp_count += 1
        next_travels = warpable(y, x)

    for travel in next_travels:
        traveling(*travel, warp_count)


traveling(ch, cw, 0)

print(reachable[dh][dw] if reachable[dh][dw] is not None else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [list(map(str, input())) for _ in range(H)]
T = [[-1 for _ in range(W)] for __ in range(H)] #その点にスタート地点から到達するためのワープの回数
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,-2,-1,0,1,2,2,-2,-2,2,-2,2,-2,-1,0,1,2]
def dfs(y,x,warp):
  # 移動Aで行けるところを埋める
  T[y][x] = warp
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < W and 0 <= ny < H:
      if S[ny][nx] != "#" and T[ny][nx] == -1:
        dfs(ny,nx,warp)
  for i in range(len(ddx)):
    nx = x + ddx[i]
    ny = y + ddy[i]
    if 0 <= nx < W and 0 <= ny < H:
      if S[ny][nx] != "#" and T[ny][nx] == -1:
        dfs(ny,nx,warp+1)
  

dfs(C[0]-1,C[1]-1,0)
print(T[D[0]-1][D[1]-1])

Submission status: Runtime Error

Solution code:
def ispossible(i,j):
    if i<0 or j<0 or i>=n or j>=m or a[i][j]=='#':
        return False
    return True
def func(i,j):
    v[i][j]=1
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(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):
                    v[i+k1][j+k2]=1
                    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):
                    v[i+k1][j+k2]=1
                    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:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def dfs(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w))
    visited = set()
    #DFS
    while path:
        p = path.pop()
        if p in visited:
            continue
        visited.add(p)
        x, y = p
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                #print("Not exist:", xx, yy)
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.append((xx, yy))
    return visited

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([False] + [True if x=='.' else False for x in input()])
    #DFS
    total_visited = set()
    visited = dfs(Ch, Cw, S, H, W)
    total_visited = total_visited.union(visited)
    if (Dh, Dw) in total_visited:
        print(0)
        exit()

    ans = 0
    while True:
        new_dist = set()
        for p in visited:
            x, y = p
            for xx, yy in [(x,y+2), (x, y-2), (x+2, y), (x-2, y)]:
                if xx<0 or yy<0 or xx>H or yy>W:
                    #print("Not exist:", xx, yy)
                    continue
                if (xx, yy) in total_visited:
                    continue
                if S[yy][xx]:
                    new_dist.add((xx, yy))
        #print(total_visited)
        #print(new_dist)
        kono = set()
        for dist in new_dist:
            x, y = dist
            if dist in total_visited:
                continue
            #print(f'new dist={x},{y}')
            new_visited = dfs(x, y, S, H, W)
            #print(f'new_visited={new_visited}')
            if new_visited:
                total_visited = total_visited.union(new_visited)
                ans += 1
                kono = kono.union(new_visited)
        if not kono:
            break
    if (Dh, Dw) in total_visited:
        print(ans)
    else:
        print(-1)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h,w=map(int,input().split())
ch, cw=map(int,input().split())
dh, dw=map(int,input().split())
m=[]
for i in range(h):
    m.append(input())
# h,w=map(int,readline().split())
# ch, cw=map(int,readline().split())
# dh, dw=map(int,readline().split())
# m=readlines()
ch-=1; cw-=1; dh-=1; dw-=1

ans=0

def valid(i, j):
    if 0<=i<=h-1 and 0<=j<=w-1:
        return True
    else:
        return False

def bfs(i, j, ans):
    #m[i][j]=str(ans)
    m[i]=m[i][:j]+str(ans)+m[i][j+1:]
    
    if (i,j)==(dh,dw):
        return 0
    
    if 0<=i-1 and (m[i-1][j]=='.' or (m[i-1][j]!='#' and int(m[i-1][j])>ans)):
        bfs(i-1, j, ans)
    if 0<=j-1 and (m[i][j-1]=='.' or (m[i][j-1]!='#' and int(m[i][j-1])>ans)):
        bfs(i, j-1, ans)
    if i+1<=h-1 and (m[i+1][j]=='.' or (m[i+1][j]!='#' and int(m[i+1][j])>ans)):
        bfs(i+1, j, ans)
    if j+1<=w-1 and (m[i][j+1]=='.' or (m[i][j+1]!='#' and int(m[i][j+1])>ans)):
        bfs(i, j+1, ans)
    
    for si in range(-2, 3):
        for sj in range(-2, 3):
            if valid(i+si, j+sj):
                if (si, sj) == (0, 0) or (si, sj) == (-1, 0) or (si, sj) == (0, -1) or (si, sj) == (1, 0) or (si, sj) == (0, 1):
                    pass
                else:
                    if m[i+si][j+sj]=='.' or (m[i+si][j+sj]!='#' and int(m[i+si][j+sj])>ans):
                        bfs(i+si, j+sj, ans+1)

bfs(ch, cw, 0)

print(m[dh][dw])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
sx,sy=map(int,input().split())
gx,gy=map(int,input().split())

if sx > gx:
  tmp1=gx
  tmp2=gy
  gx=sx
  gy=sy
  sx=tmp1
  sy=tmp2
elif sx == gx:
  if sy > gy:
    tmp=gy
    gy=sy
    sy=tmp

sx-=1
sy-=1
gx-=1
gy-=1

m=[]


for j in range(h):
    mm=list(input().split())
    m.append(mm)

ans=0
while True:

  while sx < gx and sx+1 < w -1:
    if m[sy][sx+1]=='.':
      sx+=1

  while sy < gy and sy+1 < h -1:
    if m[sy+1][sx]=='.':
      sy+=1

  if m[sy][sx+1]=='#' and m[sy+1][sx]=='#':
    if m[sy][sx+2]=='.':
      sx+=2
      ans+=1
    elif m[sy+2][sx]=='.':
      sy+=2
      ans+=1
    elif  m[sy+1][sx+1]=='.':
      sx+=1
      sy+=1
      ans+=1
    else:
      print(-1)
      break

    if sx==gx and sy==gy:
      print(ans)
      break

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
si, sj = map(lambda x: int(x) - 1, input().split())
gi, gj = map(lambda x: int(x) - 1, input().split())

maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

direction = [(-1, 0), (0, -1), (0, 1), (1, 0)]
reached_que = deque([[si, sj]])


def bfs(si, sj):
    que = deque([[si, sj]])
    reached[si][sj] += 1
    while que:
        h, w = que.popleft()
        for a, b in direction:
            next_h = h + a
            next_w = w + b
            if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
                continue
            if maze[next_h][next_w] == '#':
                continue
            if reached[next_h][next_w] != -1:
                continue
            que.append([next_h, next_w])
            reached[next_h][next_w] = reached[h][w] + 1
            reached_que.append([next_h, next_w])


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

ans = -1


def bfs2(si, sj, ans):
    for i, j in hankei_5:
        next_h = si + i
        next_w = sj + j
        if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
            continue
        if maze[next_h][next_w] == '.' and reached[next_h][next_w] == -1:
            ans += 1
            check(next_h, next_w,ans)


def check(si, sj, ans):
    bfs(si, sj)
    if reached[gi][gj] == -1:
        for r in reached_que:
            bfs2(r[0], r[1], ans)

    else:
        print(ans)
        exit(0)


check(si, sj, 0)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split()) # H: 横マス、W: 縦マス
Chw = list(map(int, input().split())) #魔法使いの現在地
Dhw = list(map(int, input().split())) #ゴール位置
Shw = [list(input()) for _ in range(H)]

dq = deque([])
visited = []
visited = [[0 for i in range(W)] for i in range(H)]
move_count = 0
ans = 0
dq.append([Chw[0], Chw[1]]) #C[0]:H, C[1]:W
visited[Chw[0]][Chw[1]] = 1
dy_dx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dy_dx_warp = [[2, 2], [2, 1], [2, 0], [1, 2], [0, 2], [1, 0], [0, 1], [1, 1], [1, -1], [-1, 0], [0, -1], [-1, -1], [-1, 1], [-1, 2], [-1, -2], [-2, 0], [-2, 1], [-2, -1], [-2, 2], [0, -2], [1, -2], [2, -1], [2, -2], [-2, -2]]
maze_count = 0
move_flg = True

while len(dq) > 0:
    now = dq.popleft()
    move_count = len(dq)
    for k in range(4):
        y = now[0] + dy_dx[k][0]
        x = now[1] + dy_dx[k][1]
        if 0 <= y < H and 0 <= x < W:
            if Shw[y][x] != '#' and visited[y][x] == 0:
                visited[y][x] = visited[now[0]][now[1]] + 1
                dq.append([y, x])
    if move_count == len(dq):
        move_flg = False
    if move_flg == False:
        for l in range(24):
            y = now[0] + dy_dx[k][0]
            x = now[1] + dy_dx[k][1]
            if 0 <= y < H and 0 <= x < W:
                if Shw[y][x] != '#' and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]] + 1
                    dq.append([y, x])
                    maze_count += 1
    move_flg = True

print(maze_count)