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: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    21st AUGUST , 2020  - FRIDAY
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def djkistra(g,st,dist): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly
    pq = []
    dist[st] = 0
    heappush(pq,(0,st))
    while(len(pq) != 0):
        curr = heappop(pq)[1]
        for i in range(0,len(g[curr])):
            b = g[curr][i][0]
            w = g[curr][i][1]
            if(dist[b] > dist[curr] + w):
                dist[b] = dist[curr]+w
                heappush(pq,(dist[b],b))

def solve():
    n,m = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    g = [[] for i in range(n*m)]

    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '#'):
                continue
            for ii in range(i-2,i+3):
                for jj in range(j-2,j+3):
                    if(ii==i and jj==j):
                        continue
                    if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
                        if(abs(ii-i)+abs(jj-j) == 1):
                            g[i*m+j].append((ii*m+jj,0))
                        else:
                            g[i*m+j].append((ii*m+jj,1))
                        # print(i*m+j,ii*m+jj)
    # for i in range(n*m):
    #     print(g[i])

    dist = [10**9]*(n*m)
    # print(x*m+y,xnot*m+ynot)
    djkistra(g,x*m+y,dist)
    # print(dist[xnot*m+ynot])
    # print(dist)
    if(dist[xnot*m+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*m+ynot])









testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
from numba import njit, b1, i4, i8, f8
import numpy as np
import numba
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    h,w = ss.shape
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if (xx if xx>=0 else -xx)+(yy if yy>=0 else -yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    21st AUGUST , 2020  - FRIDAY
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
# def djkistra(g,st,dist): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly
#     pq = []
#     dist[st] = 0
#     # pq.append([0,st]
#     heappush(pq,[0,st])
#     while(len(pq) != 0):
#         curr = heappop(pq)[1]
#         for i in range(0,len(g[curr])):
#             b = g[curr][i][0]
#             w = g[curr][i][1]
#             if(dist[b] > dist[curr] + w):
#                 dist[b] = dist[curr]+w
#                 # pq.append([dist[b],b])
#                 heappush(pq,[dist[b],b])


INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heappush(self.q, (self.dist[dest], dest))
        return self.dist


def solve():
    n,m = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    g = [[] for i in range(n*m)]

    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '#'):
                continue
            for ii in range(i-2,i+3):
                for jj in range(j-2,j+3):
                    if(ii==i and jj==j):
                        continue
                    if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
                        if(abs(ii-i)+abs(jj-j) == 1):
                            g[i*m+j].append((ii*m+jj,0))
                        else:
                            g[i*m+j].append((ii*m+jj,1))
                        # print(i*m+j,ii*m+jj)
    # for i in range(n*m):
    #     print(g[i])

    # dist = [10**9]*(n*m)
    # print(x*m+y,xnot*m+ynot)
    d = Dijkstra(g)
    dist = d.calc(x*m+y)
    # print(dist[xnot*m+ynot])
    # print(dist)
    if(dist[xnot*m+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*m+ynot])









testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

h, w = LI()
sy, sx = LI()
gy, gx = LI()
sy -= 1
sx -= 1
gy -= 1
gx -= 1
grid = SR(h)
dp = [[INF] * w for _ in range(h)]
q = deque([(sy, sx)])
dp[sy][sx] = 0
while q:
    uy, ux = q.popleft()
    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny = uy + i
        nx = ux + j
        if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "." and dp[ny][nx] > dp[uy][ux]:
            dp[ny][nx] = dp[uy][ux]
            q.appendleft((ny,nx))
    for i in range(-2, 3):
        for j in range(-2, 3):
            ny = uy + i
            nx = ux + j
            if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "." and dp[ny][nx] > dp[uy][ux] + 1:
                dp[ny][nx] = dp[uy][ux] + 1
                q.append((ny, nx))


print(dp[gy][gx] if dp[gy][gx] != INF else -1)

Submission status: Accepted

Solution code:
INF = 10**9
import sys
from heapq import *
input = sys.stdin.readline

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heappush(self.q, (self.dist[dest], dest))
        return self.dist

def sep(): return map(int,input().split())
def solve():
    h,w = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    field = []
    for i in range(h):
        temp = input().rstrip()
        field.append(temp)

    edge = [[] for i in range(h*w)]
    for i in range(h):
        for j in range(w):
            if field[i][j] == "#":
                continue
            frm = i * w + j
            for dx in range(-2, 3):
                nx = i + dx
                if nx < 0 or nx > h - 1:
                    continue
                for dy in range(-2, 3):
                    if dx == 0 and dy == 0:
                        continue
                    ny = j + dy
                    if ny < 0 or ny > w - 1:
                        continue
                    if field[nx][ny] == "#":
                        continue
                    dist = abs(dx) + abs(dy)
                    if dist == 1:
                        edge[frm].append((nx*w + ny, 0))
                    else:
                        edge[frm].append((nx*w + ny, 1))


    # for i in range(n):
    #     for j in range(m):
    #         if(grid[i][j] == '#'):
    #             continue
    #         for ii in range(i-2,i+3):
    #             for jj in range(j-2,j+3):
    #                 if(ii==i and jj==j):
    #                     continue
    #                 if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
    #                     if(abs(ii-i)+abs(jj-j) == 1):
    #                         g[i*m+j].append([ii*m+jj,0])
    #                     else:
    #                         g[i*m+j].append([ii*m+jj,1])
                        # print(i*m+j,ii*m+jj)
    # for i in range(n*m):
    #     print(g[i])

    # dist = [10**9]*(n*m)
    # print(x*m+y,xnot*m+ynot)
    d = Dijkstra(edge)
    dist = d.calc(x*w+y)
    # print(dist[xnot*m+ynot])
    # print(dist)
    if(dist[xnot*w+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*w+ynot])

solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
# visited = {}
visited = [[float("inf") for _ in range(W)] for _ in range(H)]
# visited[(cx, cy)] = 0
visited[cy][cx] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    # if (x, y) in visited and visited[(x, y)] < c:
    if visited[y][x] < c:
        # print("here1")
        continue
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
            if visited[ny][nx] <= c:
                # print("here2")
                continue
            # visited[(nx, ny)] = c
            visited[ny][nx] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                if visited[ny][nx] < c + 1:
                    # print("here3")
                    continue
                # visited[(nx, ny)] = c + 1
                visited[ny][nx] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))
# print(visited)
if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, walkable):
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    toVisit = []
    toVisit.append(start)

    currentDistance = 0
    while True:
        nextJumpOrigin = []
        while toVisit:
            p = toVisit.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue

            visited[p] = 1
            nextJumpOrigin.append(p)
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if walkable[p + d] and not visited[p + d]:
                    toVisit.append(p + d)

        # no continuous cell
        nextJump = set()
        for origin in nextJumpOrigin:
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    p = origin + dx + dy
                    if not walkable[p]:
                        continue
                    if visited[p]:
                        continue
                    nextJump.add(p)
        for p in nextJump:
            toVisit.append(p)

        currentDistance += 1
        if not toVisit:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, walkable):
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    toVisit = []
    toVisit.append(start)

    currentDistance = 0
    while True:
        nextJumpOrigin = []
        while toVisit:
            p = toVisit.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue

            visited[p] = 1
            nextJumpOrigin.append(p)
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if walkable[p + d] and not visited[p + d]:
                    toVisit.append(p + d)

        # no continuous cell
        nextJump = set()
        for origin in nextJumpOrigin:
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    p = origin + dx + dy
                    if not walkable[p]:
                        continue
                    if visited[p]:
                        continue
                    if p in nextJump:
                        continue
                    nextJump.add(p)
        for p in nextJump:
            toVisit.append(p)

        currentDistance += 1
        if not toVisit:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()