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: Wrong Answer

Solution code:

import numpy as np
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


Ss = [list(input()) for _ in range(H)]
Ss = np.array(Ss)

Ss_num = np.zeros(Ss.shape, dtype=int)
warp_counts = np.zeros(Ss.shape, dtype=int)
unvisiteds = np.zeros(Ss.shape, dtype=int)


for i in range(H):
    for j in range(W):
        Ss_num[i][j] = 1 if Ss[i][j] == "." else 0
        unvisiteds[i][j] = 1 if Ss[i][j] == "." else 0






from collections import deque
queue = deque()





queue.append((Ch, Cw))

def valid_pos(pos):
    return 0 <= pos[0] and pos[0] < H and\
        0 <= pos[1] and pos[1] < W

def pos_around(pos):
    return [
        (pos[0]-1, pos[1]),
        (pos[0],   pos[1]-1),
        (pos[0]+1, pos[1]),
        (pos[0],   pos[1]+1),
    ]

current_warp_count = 0
while True:
    
    edges = set()
    while len(queue) > 0:
        pos = queue.popleft()
        unvisiteds[pos] = 0
        warp_counts[pos] = current_warp_count

        if pos[0] == Dh and pos[1] == Dw:
            print(current_warp_count)
            exit(0)
        
        for new_pos in pos_around(pos):
            
            if valid_pos(new_pos)==False:
                continue

            
            if Ss_num[new_pos] == 1 and unvisiteds[new_pos]==1:
                queue.append(new_pos)
                unvisiteds[new_pos] = 0

            if Ss_num[new_pos] == 0:
                # print(new_pos, pos)
                edges.add(pos)

        
    # print(edges)
    warp_candidate = set()
    # search can go '.' with warp  
    for edge in edges:
        edge_h = edge[0]
        edge_w = edge[1]
        
        hmin=max(0,edge_h-2)
        hmax=min(H,edge_h+3)
        wmin=max(0,edge_w-2)
        wmax=min(W,edge_w+3)
        Ss_num_area = Ss_num[hmin:hmax,wmin:wmax]
        unvisited_area = unvisiteds[hmin:hmax,wmin:wmax]
        # print(edge)
        # print(Ss_num_area)
        # print(unvisited_area)
        mul =  Ss_num_area * unvisited_area
        

        if mul.sum().sum()>0:
            for i in range(mul.shape[0]):
                for j in range(mul.shape[1]):
                    if mul[i][j] == 1:
                        warp_candidate.add((i,j))

        
    if len(warp_candidate) == 0:
        print(-1)
        exit(0)
    
    for candidate in warp_candidate:
        queue.append(candidate)
    current_warp_count += 1

Submission status: Wrong Answer

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, e = 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, e+1))
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		#print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						elif S[x+t][y+2*yy]=="#":
							continue
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						elif S[x+2*xx][y+t]=="#":
							continue
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]==d:
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[1000000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if check_position(neh, new, now_warp+1):
                next_p.append([neh, new])
    return next_p


def check_position(hi, wi, now_warp):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1 or visited[hi][wi] <= now_warp:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    warp_positions = deque()
    while len(positions)>0:
        nh, nw, now_warp = positions.popleft()

        if now_warp >= visited[nh][nw]:
            continue

        visited[nh][nw] = now_warp
        move_cnt = 0
        if check_position(nh+1, nw, now_warp):
            positions.append([nh+1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw+1, now_warp):
            positions.append([nh, nw+1, now_warp])
            move_cnt += 1
        
        if check_position(nh-1, nw, now_warp):
            positions.append([nh-1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw-1, now_warp):
            positions.append([nh, nw-1, now_warp])
            move_cnt += 1

        if move_cnt<4:
            warp_positions.append([nh, nw, now_warp])
    
    while len(warp_positions)>0:
        nh, nw, now_warp = warp_positions.popleft()
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==100000 else visited[gh-1][gw-1])

Submission status: Wrong Answer

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)

    memo2 = []
    for _ in range(H):
        tmp = []
        for __ in range(W):
            tmp.append(1001001001)
        memo2.append(tmp)
    memo2[end[0]][end[1]] = 0
    # print(memo)
    q = Queue()
    q.put(end)
    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 memo2[x][y] <= memo2[p[0]][p[1]] + 1:
                    continue
                memo2[x][y] = memo2[p[0]][p[1]] + 1
                q.put((x,y))
    total = 1001001001
    for i in range(H):
        for j in range(W):
            if memo[i][j] == 1001001001:
                continue
            if memo2[i][j] == 1001001001:
                continue
            total = min(total, memo2[i][j])
    # print(*memo, sep="\n")
    print(total)

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

Submission status: Wrong Answer

Solution code:
import collections
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
s = [input() for _ in range(h)]
table = [[float('inf') for _ in range(w)] for _ in range(h)]
table[Ch][Cw] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
used = [[0 for _ in range(w)] for _ in range(h)]
used[Ch][Cw] = 1
que = collections.deque()
que.append([Ch, Cw])

def bfs(Q):
    while Q:
        # print(Q)
        v = Q.popleft()
        i = v[0]
        j = v[1]
        for k in range(4):
            if 0 <= i+dy[k] < h and 0 <= j+dx[k] < w:
                if s[i+dy[k]][j+dx[k]] == '.':
                    if used[i+dy[k]][j+dx[k]] == 0:
                        table[i+dy[k]][j+dx[k]] = table[i][j]
                        used[i+dy[k]][j+dx[k]] = 1
                        Q.append([i+dy[k], j+dx[k]])
        # magic
        for a in range(-2, 3):
            for b in range(-2, 3):
                if 0 <= i+a < h and 0 <= j+b < w:
                    if s[i+a][j+b] == '.':
                        table[i+a][j+b] = min(table[i][j]+1, table[i+a][j+b])
        # print(*table, sep='\n')
        # print(*used, sep='\n')
        # print(*s, sep='\n')

bfs(que)
while True:
    for i in range(h):
        for j in range(w):
            if used[i][j] == 0 and table[i][j] != float('inf'):
                que = collections.deque()
                que.append([i, j])
                bfs(que)
                continue
    break

if table[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(table[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
                    wroute.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    P = [[-1 for _ in range(W)] for h in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] == -1 and S[h][w] == ".":
                q.append((h, w))
                while q:
                    ch, cw = q.popleft()
                    if P[ch][cw] == -1:
                        P[ch][cw] = count
                        for dh, dw in move:
                            if 0<=ch+dh<H and 0<=cw+dw<W and S[ch+dh][cw+dw] == "." and P[ch+dh][cw+dw] == -1:
                                q.append((ch+dh, cw+dw))
                count += 1
    nm = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0: continue
            else: nm.append((i, j))
    q.append((0, sh, sw))
    D = [[-1 for w in range(W)] for h in range(H)]
    while q:
        d, ch, cw = q.popleft()
        if D[ch][cw] == -1:
            D[ch][cw] = d
            for dh, dw in nm:
                if 0<=ch+dh<H and 0<=cw+dw<W and S[ch+dh][cw+dw] == "." and D[ch+dh][cw+dw] == -1:
                    if P[ch][cw] == P[ch+dh][cw+dw]: q.append((d, ch+dh, cw+dw))
                    else: q.append((d+1, ch+dh, cw+dw))
    print(D[fh][fw])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://atcoder.jp/contests/arc033/submissions/me
# https://atcoder.jp/contests/abc174/tasks/abc174_f
#
# speed up TIPS: delete update of el. non-use of getitem, setitem.
#
# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get bound of index where x1+x2+...+xi<w

class Bit: # 1-indexed
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): # 0-indexed
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nb=[-2*w+1,-2*w+2,-w+1,-w+2,1,2,2*w+1,2*w+2,w+1,w+2,+w,+2*w,-w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,1,2,2*w-1,2*w-2,w-1]

u=[-1]*cn
for i in range(n):
    if m[i]==1:
        continue
    u[dc[v[i]]]=1
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and dc[v[i]]!=dc[v[nx]]:
            g[dc[v[i]]].add(dc[v[nx]])

q=[dc[v[sh*w+sw]]]
dist=[-1]*cn
dist[dc[v[sh*w+sw]]]=0
while q:
    c=q.pop()
    for nx in g[c]:
        if dist[nx]==-1:
            q+=nx,
            dist[nx]=dist[c]+1

print(dist[dc[v[gh*w+gw]]])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						elif S[x+t][y+2*yy]=="#":
							continue
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						elif S[x+2*xx][y+t]=="#":
							continue
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]==d:
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()