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
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from collections import deque
import numpy as np
from itertools import permutations


class Lab:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.map = np.zeros(shape=(h, w), dtype=np.int8)
        self.max_c = 1
        self.tree = dict()

    def set_wall(self, ih, walls):
        self.map[ih] = walls

    def bfs(self, y, x, c):
        q = deque()
        p = y * 10000 + x
        q.append(p)
        visited = set()
        visited.add(p)

        while q:
            v = q.popleft()
            y, x = divmod(v, 10000)
            self.map[y][x] = c
            for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ny, nx = y+dy, x+dx
                if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                    continue
                if self.map[ny][nx] != 0:
                    continue
                p = ny * 10000 + nx
                if p in visited:
                    continue
                q.append(p)
                visited.add(p)

    def coloring(self):
        for y in range(self.h):
            for x in range(self.w):
                if self.map[y][x] == 0:
                    self.max_c += 1
                    self.bfs(y, x, self.max_c)

    def room(self):
        if self.max_c == 1:
            return

        for c in range(2, self.max_c+1):
            self.tree[c] = set()

        for y in range(self.h):
            for x in range(self.w):
                c = self.map[y][x]
                if c == 1:
                    continue
                for dy in range(-2, 3):
                    for dx in range(-2, 3):
                        ny, nx = y + dy, x + dx
                        if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                            continue
                        tc = self.map[ny][nx]
                        if tc not in (1, c):
                            self.tree[c].add(tc)


def solve():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1

    lab = Lab(h, w)
    for i in range(h):
        walls = np.array(list(map(lambda x: int(x == "#"), input())))
        lab.set_wall(i, walls)

    lab.coloring()
    # print(lab.map)
    dc = lab.map[dh][dw]
    if dc == 1:
        return "-1"

    cc = lab.map[ch][cw]
    if dc == cc:
        return 0

    lab.room()
    # print(lab.tree)
    ct = lab.tree[cc]
    if dc in ct:
        return 1
    #
    # lab.tree.pop(cc)
    # pre_set = ct
    # min_dist = 10 ** 9
    # for roots in permutations(lab.tree):
    #     # print(roots)
    #     dist = 0
    #     ok = False
    #     for nc in roots:
    #         if nc not in pre_set:
    #             break
    #         dist += 1
    #         if dc in pre_set:
    #             ok = True
    #             break
    #         pre_set = lab.tree[nc]
    #     if ok:
    #         min_dist = min(min_dist, dist)
    #
    # if min_dist == 10 ** 9:
    #     return "-1"
    #
    # return min_dist
    return 0


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h, w  =map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
field = [list(input()) for _ in range(h)]

cx -= 1
cy -= 1
dx -= 1
dy -= 1

ans = -1
dist_x = [-1, 0, 0, 1]
dist_y = [0, -1, 1, 0]

def start(x, y):
    field[x][y] = 'S'
    for i in range(4):
        nx = x + dist_x[i]
        ny = y + dist_y[i]
        if nx >= 0 and nx < h and ny >= 0 and ny < w and field[nx][ny] == '.':
            start(nx, ny)

def goal(x, y):
    ok = False
    if field[x][y] == 'S':
        ok = True
    else:
        field[x][y] = 'G'

    for i in range(4):
        nx = x + dist_x[i]
        ny = y + dist_y[i]
        if nx >= 0 and nx < h and ny >= 0 and ny < w and field[nx][ny] == '.':
            goal(nx, ny)
    return ok


def warp(x, y, arrive_depth):
    field[x][y] = 'W'
    if field[x][y] == 'G':
        return arrive_depth
    
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x + i
            ny = y + j
            if nx >= 0 and nx < h and ny >= 0 and ny < w and field[nx][ny] != 'S' and field[nx][ny] != '#' and field[nx][ny] != 'W':
                arrive_depth += 1
                warp(nx, ny, arrive_depth)
    return arrive_depth

start(cx, cy)

if goal(dx, dy):
    ans = 0
else:
    ans = 1001001001
    for i in range(h):
        for j in range(w):
            if field[i][j] == 'S':
                tmp = warp(i, j, 0)
                if tmp > 0 and tmp < ans:
                    ans = tmp

if ans == 1001001001:
    ans = -1

print(ans)

# for i in range(h):
#    print(field[i])

Submission status: Runtime Error

Solution code:
hw=input("").split(" ")
h=int(hw[0])
w=int(hw[1])
hhh=input("").split(" ")
ch=int(hhh[0])-1
dh=int(hhh[1])-1
www=input("").split(" ")
cw=int(www[0])-1
dw=int(www[1])-1
liss=[]
lisc=[]
for _1 in range(h):
    tmplis1=[]
    tmplis3=[]
    tmplis2=input("")
    for i in tmplis2:
        tmplis1+=[i]
        if(i=="#"):
            tmplis3+=[-1]
        else:
            tmplis3+=[1000]
    
    lisc+=[tmplis3]
    liss+=[tmplis1]
    
frag1=0
baket=[[ch,cw]]
nbaket=[]
step=0
lisc[ch][cw]==0
while(lisc[dh][dw]==1000 and frag1==0):
    cnt=0
    while(len(baket)>cnt):
        tmp=baket[cnt]
        tmp1=tmp[0]
        tmp2=tmp[1]
        
        if(tmp2<w-1 and lisc[tmp1][tmp2+1]==1000):
            lisc[tmp1][tmp2+1]==step
            baket+=[[tmp1,tmp2+1]]
        
        
        if(tmp2>0 and lisc[tmp1][tmp2-1]==1000):
            lisc[tmp1][tmp2-1]==step
            baket+=[[tmp1,tmp2-1]]
        if(tmp1<h-1 and lisc[tmp1+1][tmp2]==1000):
            lisc[tmp1+1][tmp2]==step
            baket+=[[tmp1+1,tmp2]]
        if(tmp1>0 and lisc[tmp1-1][tmp2]==1000):
            lisc[tmp1-1][tmp2]==step
            baket+=[[tmp1-1,tmp2]]
        cnt+=1
    step+=1
    for i in baket:
        for ii in range(-2,3):
            for iii in range(-2,3):
                itm1=i[0]+ii
                itm2=i[1]+iii
                if (itm1<h-1 and itm1>-1 and itm2<w-1 and itm2>-1 and lisc[itm1][itm2]==1000):
                    lisc[itm1][itm2]=step
                    nbaket+=[[itm1,itm2]]
    if(len(nbaket)==0):
        frag1=1
    baket=nbaket
if(lisc[dw][dh]==1000):
    print(-1)
else:
    print(lisc[dw][dh])

Submission status: Runtime Error

Solution code:
from collections import deque
from sys import stdin, setrecursionlimit
input = stdin.readline

setrecursionlimit(100000)

def DFS(x,y):
    #global blocknum
    if mapmatrix[y][x] == '.' and blocknumlist[y][x] == -1:
        #blocknumlist[y][x] = blocknum
        num = blocknumlist[y][x]
        for dx, dy in move:
            X = x + dx; Y = y + dy
            if X == Dw and Y == Dh:
                print(num)
                exit()
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blocknumlist[Y][X] == -1 and mapmatrix[Y][X] == '.':
                    blocknumlist[Y][X] = num
                    DFS(X,Y)
        for dx, dy in move2:
            X = x + dx; Y = y + dy
            if X == Dw and Y == Dh:
                print(num + 1)
                exit()
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blocknumlist[Y][X] == -1 and mapmatrix[Y][X] == '.':
                    blocknumlist[Y][X] = num + 1
                    DFS(X,Y)

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
mapmatrix = [None]*H
for i in range(H):
    mapmatrix[i] = list(input())

move = ((1,0),(-1,0),(0,-1),(0,1))
move2 = ((2,0),(-2,0),(0,-2),(0,2),(1,1),(-1,-1),(1,-1),(-1,1))
blocknumlist = [[-1]*W for _ in range(H)]
blocknum = 0

DFS(Cw,Ch)
print(-1)

Submission status: Runtime Error

Solution code:
import heapq
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def Walk(X, Y):
    return [[X-1, Y], [X+1, Y], [X, Y-1], [X, Y+1]]

def Magic(X, Y):
    Ret = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            Ret.append([X+x, Y+y])
    return Ret

D = [[float("inf")]*W for _ in range(H)]
D[Ch-1][Cw-1] = 0

Used = [[False]*W for _ in range(H)]

que = [(0, [Ch-1, Cw-1])]
while que:
    c, pos = heapq.heappop(que)
    if Used[pos[0]][pos[1]]:
        continue
    D[pos[0]][pos[1]] = c
    Used[pos[0]][pos[1]] = True
    if Dh - 1 == pos[0] and Dw -1 == pos[1]:
        break
    for pos_to in Magic(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    Step = abs(pos_to[0]-pos[0]) + abs(pos_to[1]-pos[1])
                    if Step == 0:
                        continue
                    elif Step == 1:
                        heapq.heappush(que, (c, pos_to))
                    else:
                        if D[pos_to[0]][pos_to[1]] > c+1
                            heapq.heappush(que, (c+1, pos_to))
if D[Dh-1][Dw-1] == float("inf"):
    print(-1)
else:
    print(D[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque
infty = 10 ** 9 #適宜設定する

'''
def jump(row, col):
    for j in range ()
'''

def SCC(graph, component, H, W):
    visited = [False for i in range(H*W)]
    component_num = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == "." and not visited[i*H+j]:
                BFS_recursion(graph, visited, component, component_num, i*H+j)
                component_num += 1
    compressed_graph = [[] for i in range(component_num - 1)]
    s = ""
    for j in range (W+4):
        s += "#"
    S_extended = [s, s]
    for i in range(H):
        S_extended.append("##" + S[i] + "##")
    S_extended.append(s)
    S_extended.append(s)
    for i in range(H):
        for j in range(W):
            for k in range(5):
                for l in range(5):
                    if S_extended[i+k][j+l] == "." and component[(i+k)*H+j+k] != component[i*H+j]:
                        compressed_graph[component[i*H+ j]].append(component[(i+k)*H + j+k])
                        compressed_graph[component[(i+k)*H +j+k]].append(component[i*H+j])
    for i in range(component_num-1):
        compressed_graph[i] = list(set(compressed_graph[i]))
    return (compressed_graph, component_num - 1)

def BFS_recursion(G, visited, component, component_num, u):
    queue = deque()
    queue.append(u)
    L = 1
    visited[u] = True
    component[u] = component_num
    while queue:
        add_v = 0 
        while L > 0:
            v = queue.popleft()
            visited[v] = True
            component[v] = component_num
            L -= 1
            for j in G[v]:
                if not visited[j]:
                    queue.append(j)
                    visited[j] = True
                    add_v += 1
        L = add_v

def BFS2(G, D, u):
    queue = deque()
    queue.append(u)
    visit = [False for k in range(len(D))]
    d = 0
    L = 1
    visit[u] = True
    while queue:
        add_v = 0 
        while L > 0:
            v = queue.popleft()
            D[v] = d
            L -= 1
            for j in G[v]:
                if not visit[j]:
                    queue.append(j)
                    visit[j] = True
                    add_v += 1
        d += 1
        L = add_v
    return D


H, W = map(int, input().split())
C_H, C_W = map(int, input().split())
D_H, D_W = map(int, input().split())

graph = [[] for i in range(H * W)]
S = []
for i in range(H):
    S.append(input())

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0 and S[i - 1][j] == ".":
                graph[i * H + j].append((i-1)*H + j)
            if j != 0 and S[i][j-1] == ".":
                graph[i * H + j].append(i*H + j-1)
            if i != H-1 and S[i+1][j] == ".":
                graph[i*H+j].append((i+1)*H +j)
            if j != W-1 and S[i][j+1] == ".":
                graph[i*H+j].append(i*H + j+1)

component = [-1 for i in range(H*W)]

compressed_graph, component_num = SCC(graph, component, H, W)
dist = [infty for i in range(component_num)]
BFS2(compressed_graph, component[(C_H -1)*H+C_W -1])

print(dist[component[(D_H - 1)*H+D_W - 1]])

Submission status: Runtime Error

Solution code:
h, w, m = map(int, input().split())

bomb = []
for i in range(m):
    bomb.append(list(map(int, input().split())))
    
sum_hor, sum_ver = {}, {}
for i in range(m):
    h_i = bomb[i][0]-1
    w_i = bomb[i][1]-1
    if h_i not in sum_hor:
        sum_hor[h_i] = 1
    else:
        sum_hor[h_i] += 1
    if w_i not in sum_ver:
        sum_ver[w_i] = 1
    else:
        sum_ver[w_i] += 1

cost = []
for i in sum_hor.keys():
    for j in sum_ver.keys():
        if bomb[i][j] == 1:
            cost.append(sum_hor[i] + sum_ver[j] - 1)
        else:
            cost.append(sum_hor[i] + sum_ver[j])
print(max(cost))

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

CH -= 1
CW -= 1
DH -= 1
DW -= 1


MAP = []
state = 1
ans = 0
for i in range(H):
    MAP.append(list(input()))


while True:

    state = 1
    # 上下で目的地にたどり着けるか
    if CH > DH and MAP[CW][CH-1] != "#" and 0 <= CH:
        CH -= 1
        state = 0

    if CH < DH and MAP[CW][CH+1] != "#" and H >= CH:
        CH += 1
        state = 0


    # 左右で目的地にたどり着けるか
    if CW > DW and MAP[CW-1][CH] != "#" and 0 <= CW:
        CW -= 1
        state = 0
    if CW < DW and MAP[CW+1][CH] != "#" and W >= CW:
        CW += 1
        state = 0

    # ワープ時の処理
    if state == 1:
        # 右下にワープ
        if CH <= DH and CW <= DW:
            for i in range(1,3):
                for j in range(1,3):
                    if MAP[CH+i][CW+j] == "." and CH+i >= H and CW+j >= W:
                        CH += i
                        CW += j
                        state = 0
                        ans += 1
        # 右上にワープ
        if CH >= DH and CW <= DW:
            for i in range(-1,-3,-1):
                for j in range(1,3):
                    if MAP[CH+i][CW+j] == "." and CH+i <= 0 and CW+j >= W:
                        CH += i
                        CW += j
                        state = 0
                        ans += 1
        # 左上にワープ
        if CH >= DH and CW >= DW:
            for i in range(-1,-3,-1):
                for j in range(-1,-3,-1):
                    if MAP[CH+i][CW+j] == "." and CH+i <= 0 and CW+j <= 0:
                        CH += i
                        CW += j
                        state = 0
                        ans += 1
        # 左下にワープ
        if CH <= DH and CW >= DW:
            for i in range(1,3):
                for j in range(-1,-3,-1):
                    if MAP[CH+i][CW+j] == "." and CH+i >= H and CW+j <= 0:
                        CH += i
                        CW += j
                        state = 0
                        ans += 1

        # それでもダメだったら
        if state == 1:
            ans = -1
            print(ans)
            exit(0)

    if CH == DH and CW == DW:
        print(ans)
        exit(0)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh -= 1
sw -= 1
gh, gw = list(map(int, input().split()))
gh -= 1
gw -= 1
lst = []
for _ in range(H):
    lst.append(list(str(input())))
    
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
visited = [[0]*W for _ in range(H)]

def dfs(sh, sw):
    global visited
    global flg
    flg = 0
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    c = 0
    while stack:
        sh, sw = stack.pop()
        if sh == gh and sw  == gw:
            flg = 1
            break
        for i in range(4):
            nx = sh + dx[i]
            ny = sw + dy[i]
            if 0 > nx or nx >= H or 0 > ny or ny >= W:
                continue
            else:
                if lst[nx][ny] == '#' or visited[nx][ny] == 1:
                    continue
                else:
                    visited[nx][ny] = 1
                    stack.append([nx, ny])

c = lst.count('.')
ans = 0

dfs(sh, sw)

if visited[gh][gw]:
    print(ans)
ov = -1
nv = - 2
while ov != nv:
    ov = sum(visited[gh][gw], []).count(1)
    for h in range(H):
        for w in range (W):
            if visited[h][w] == 0 and lst[h][w] != '#':
                arr = np.array(visited)[max(0, h-2):min(H, h+3),max(0, w-2):min(W, w+3)].tolist()
                if sum(arr, []).count(1) >= 1:
                    ans += 1
                    dfs(h,w)
                    nv = sum(visited[gh][gw], []).count(1)
                    if flg:
                        break
                
if visited[gh][gw]:
    print(ans)
else:
    print(-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_[h+3])):
        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())

group_conect={}
for g in group.keys():
    group_conect[g] = set([])
    
break_flag = False
for g_1 in range(1,group_+1):
    for g_2 in range(g_1+1,group_+1):
        for g1 in group[g_1]:
            for g2 in group[g_2]:
                y,x = get_position(g1)
                y_min = max(0,y-2)
                y_max = min(W,y+2)
                x_min = max(0,x-2)
                x_max = min(H,x+2)
                Y,X = get_position(g2)

                if y_min <= Y and Y <= y_max and x_min <= X and X <= x_max:
                    group_conect[g_1].add(g_2)
                    group_conect[g_2].add(g_1)
                    break
print(group_conect)

Submission status: Runtime Error

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    H, W = mulinputs()
    start = tuple(mulinputs())
    end = tuple(mulinputs())
    maze = []
    for h in range(H):
        maze.append([c for c in input()])

    ans = [
        [0, 1, INF, INF],
        [1, 2, INF, INF],
        [2, INF, INF, INF],
        [3, INF, INF, INF]
    ]
    start = (start[0] -1 , start[1] -1)
    end = (end[0] - 1, end[1] - 1)
    # memo = [[1001001001]*W]*H
    memo = []
    for _ in range(H):
        tmp = []
        for __ in range(W):
            tmp.append(1001001001)
        memo.append(tmp)
    visited = [[False]*W]*H
    x, y = 0, 1
    # visited[start[0]][start[1]] = True
    # print(memo)
    # print(memo[0][0])
    memo[start[0]][start[1]] = 0
    # print(memo)
    q = Queue()
    q.put(start)
    while not q.empty():
        p = q.get()
        # if memo[p[0]][p[1]] > -1:
        #     continue
        for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x, y = p[0] + d[0], p[1] + d[1]
            if x < 0 or y < 0 or x >= H or y >=W:
                continue
            if maze[x][y] == '#':
                continue
            if memo[x][y] <= memo[p[0]][p[1]] + 1:
                continue
            memo[x][y] = memo[p[0]][p[1]] + 1
            q.put((x,y))


    if memo[end[0]][end[1]] != 1001001001:
        print(0)
        exit()

    mmm = 0
    tt = None
    for i in range(H):
        for j in range(W):
            if memo[i][j] == 1001001001:
                continue
            if mmm < memo[i][j]:
                mmm = memo[i][j]
                tt = (i, j)

    memo = []
    for _ in range(H):
        tmp = []
        for __ in range(W):
            tmp.append(1001001001)
        memo.append(tmp)
    visited = [[False]*W]*H
    # visited[start[0]][start[1]] = True
    # print(memo)
    # print(memo[0][0])
    memo[tt[0]][tt[1]] = 0
    # print(memo)
    q = Queue()
    q.put(tt)
    while not q.empty():
        p = q.get()
        # if memo[p[0]][p[1]] > -1:
        #     continue
        # for d in [(-2, -2), (1, 0), (0, -1), (0, 1)]:
        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                x, y = p[0] + i, p[1] + j
                if x < 0 or y < 0 or x >= H or y >=W:
                    continue
                # if maze[x][y] == '#':
                #     continue
                if memo[x][y] <= memo[p[0]][p[1]] + 1:
                    continue
                memo[x][y] = memo[p[0]][p[1]] + 1
                q.put((x,y))
    # print(*memo, sep="\n")
    print(memo[end[0]][end[1]])

                
    # # 出力
    # print(datas)
    # print(yn[not judge::2])
    # print(cnt)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()

d = [[0, -1], [1, 0], [0, 1], [-1, 0]]
ans = 0
stock 
root_list = []
def dfs(start_h, start_w, r2):
    a[start_h][start_w] = '#'
    if (start_h==Dh) && (start_w==Dw):
        return True
    for i in range(-2, 3):
        for j in range(-2, 3):
            if ((i<-1)||(i>1)) && ((j<-1)||(j>1)):
                s_h = start_h+i; s_w = start_w+j
                if(0<=(start_h+i)<h) && (0<=(start_w+j)<w):
                    if a[s_h][s_w]=='.':
                        root_list.append([s_h, s_w, ans])
    for i in d:
        next_h=start_h+i[0]; next_w=start_w+i[1]
        if(0<=next_h<h) && (0<=next_w<w) && (a[next_h][next_w]=='.')):
            dfs(next_h, next_w, root_list)
def main():
    if(dfs(Ch, Cw, 0)):
        print(0)
        return
    while root_list:
        r0 = root_list[0][0]; r1 = root_list[0][1]; r2=root_list[0][2]+1
        root_list.pop(0)
        if a[r0][r1] == '.':
            root_list[2]
            if dfs(r0, r1, r2):
                print(r2)
                break
    print(-1)