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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    from time import time
    st = time()
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    while q:
        nh, nw = q.popleft()
        now = c[(nh, nw)]
        for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            mh += nh
            mw += nw
            if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                c[(mh, mw)] = now
                q.appendleft((mh, mw))
        for i in range(-2, 3):
            i += nh
            for j in range(-2, 3):
                j += nw
                if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and s[i][j] == ".":
                    c[(i, j)] = now + 1
                    q.append((i, j))
        if time() - st >= 1.8:
            print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
            return
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = []
stc2 = []
a = 0
while(1):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > a+1):
        a += 1
        c = stc1[a][0]
        d = stc1[a][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            a = 0
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
DDX = (-1, 0, 1, 0, -1, -1, 1, 1)
DDY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DDX[:4]
DY = DDY[:4]


H, W = map(int, input().split())
Cx, Cy = map(int, input().split())
Dx, Dy = map(int, input().split())

grid = ["#" * (W + 2)]
for _ in range(H):
    inp = "#" + input().strip() + "#"
    grid.append(inp)
grid.append("#" * (W + 2))


area = [[-1] * (W + 2) for _ in range(H + 2)]
cnt = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "#" or area[i][j] != -1:
            continue
        cnt += 1
        node = [(i, j)]
        area[i][j] = cnt
        while node:
            x, y = node.pop()
            for dx, dy in zip(DX, DY):
                nx = x + dx
                ny = y + dy
                if grid[nx][ny] == "#":
                    continue
                if area[nx][ny] == -1:
                    area[nx][ny] = cnt
                    node.append((nx, ny))


used = defaultdict(int)

edge = [[] for _ in range(cnt + 1)]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == ".":
            continue
        memo = set()
        for dx, dy in zip(DDX, DDY):
            if area[i + dx][j + dy] == -1:
                continue
            memo.add(area[i + dx][j + dy])
        for x, y in combinations(memo, 2):
            if x > y:
                x, y = y, x
            if used[(x, y)]:
                continue
            edge[x].append(y)
            edge[y].append(x)
            used[(x, y)] = 1


dist = [-1] * (cnt + 1)
ci = area[Cx][Cy]
di = area[Dx][Dy]
dist[ci] = 0
node = deque([ci])
while node:
    s = node.popleft()
    for t in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = dist[s] + 1
        node.append(t)

print(dist[di])

Submission status: Wrong Answer

Solution code:
#create date: 2020-08-22 21:07

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    inf = 10**10
    h, w = na()
    ch, cw = na()
    ddh, ddw = na()
    g = '#' * (w + 4)
    g += '#' * (w + 4)
    for _ in range(h):
        g += '##' + ns() + '##'
    g += '#' * (w + 4)
    g += '#' * (w + 4)
    maze = [[inf] * (w+1) for i in range(h+1)]
    q = deque()
    p = deque([(ch, cw)])
    maze[ch][cw] = 0
    move = (1, 0), (0, 1), (-1, 0), (0, -1)
    jump = (2, -2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -2), (1, 2), (0, -2), (0, 2), (-1, -2), (-1, 2), (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2)
    #print(len(g), g)

    while p:
        #jump
        r = p.popleft()
        #print(r)
        q.append(r)
        while q:
            # move
            nh, nw = q.popleft()
            for ih, iw in move:
                dh, dw = nh + ih, nw + iw
                #print(dh, dw, dh*(w+4) + dw+1)
                if g[(dh-1+2)*(w+4) + dw+1] == ".":
                    #print(dh, dw, dh*(w+4) + dw+1, g[:(dh-1+2)*(w+4) + dw+1+1])
                    if maze[dh][dw] != maze[nh][nw]:
                        q.append((dh, dw))
                        maze[dh][dw] = min(maze[dh][dw], maze[nh][nw])
            for ih, iw in jump:
                dh, dw = nh + ih, nw + iw
                if g[(dh-1+2)*(w+4) + dw+1] == ".":
                    if maze[dh][dw] > maze[nh][nw]+1:
                        p.append((dh, dw))
                        maze[dh][dw] = min(maze[dh][dw], maze[nh][nw]+1)
    #print(maze)
    if maze[ddh][ddw] == inf:
        print(-1)
    else:
        print(maze[ddh][ddw])



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+1, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+1, x) ):
            flag_searched[i][j] = True
            if(Mazes[i][j] == "."):
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    #print(road_types)
    for i in range(H):
        for j in range(W):
            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                for dy in range(-2, 3, 1):
                    for dx in range(-2, 3, 1):
                        if(-1< i+dy and i+dy < H and -1< j+dx and j+dx < W and flag_searched[i+dy][j+dx]==False):
                            flag_searched[i+dy][j+dx] = True

                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)
    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
from collections import deque
mod = 10**9 + 7

def main():
  h, w = I()
  ch, cw = I()
  dh, dw = I()
  s = ['$'*(w+4)]*(h+4)
  for i in range(h):
    s[i+2] = '$$' + input() + '$$'

  dist = [[-1]*(w+4) for _ in range(h+4)]
  dist[ch + 1][cw + 1] = 0
  q = deque()
  q.append((ch+1, cw+1))
  while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    flag = [False, False, False, False]
    for i in range(4):
      nx = x + vx[i]
      ny = y + vy[i]
      if s[nx][ny] == '$': 
        flag[i] = True
        continue # 壁なら通れないね！
      if s[nx][ny] == '#':
        flag[i] = True
        continue
      if dist[nx][ny] != -1: 
        flag[i] = True
        continue # もう最短距離がわかってるなら飛ばす
      dist[nx][ny] = dist[x][y]
      q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく
    if not False in flag: # もし4つのflagがTrueの時5×5以内に飛べるか探す
      vvx = [-2,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2]
      vvy = [0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2,1,1,1,1,2,2,2,2,2]
      for i in range(20):
        nnx = x + vvx[i]
        nny = y + vvy[i]
        if s[nnx][nny] == '$': 
          continue # 壁なら通れないね！
        if s[nnx][nny] == '#':
          continue
        if dist[nnx][nny] != -1:
          if dist[nnx][nny] > dist[x][y]:
            dist[nnx][nny] = dist[x][y] + 1
          continue # もう最短距離がわかってるなら飛ばす
        dist[nnx][nny] = dist[x][y] + 1
        q.append((nnx, nny))
  print(s)
  print(dist)
  
  print(dist[dh+1][dw+1])

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=deque([[a-1,b-1,0]])
mi=inf
while(stack):
    xx,yy,cost=stack.popleft()
    vis[xx][yy]=1

    if xx==x and yy==y:
        mi=min(mi,cost)

    for i in range(-2,3,1):
        for j in range(-2, 3, 1):


            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    stack.append([xx+i,yy+j,cost])
                else:
                    stack.append([xx + i, yy + j, cost+1])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = LIST()
D = LIST()
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
dist = [[INF] * W for i in range(H)]
q = deque([(C[0]-1, C[1]-1)])

dist[C[0]-1][C[1]-1] = 0
visited[C[0]-1][C[1]-1] = True
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
warp = [[-1] * W for i in range(H)]
warp[C[0]-1][C[1]-1] = 0
warp_time = 0
warp_stock = deque([])

while q:
    while q:
        ch, cw = q.popleft()
        warp_stock.append([ch, cw])
        dh = [0, 1, 0, -1]
        dw = [1, 0, -1, 0]
        for i in range(4):
            nh = ch + dh[i]
            nw = cw + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == False and S[nh][nw] != "#":
                    # dist[nh][nw] = dist[ch][cw] + 1
                    visited[nh][nw] = True
                    warp[nh][nw] = warp_time
                    q.append([nh, nw])
    while warp_stock:
        ch, cw = warp_stock.popleft()
        for dh in [-2, -1, 0, 1, 2]:
            for dw in [-2, -1, 0, 1, 2]:
                nh = ch + dh
                nw = cw + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == False and S[nh][nw] != "#":
                        # dist[nh][nw] = dist[ch][cw]
                        visited[nh][nw] = True
                        q.append([nh, nw])
                        warp[nh][nw] = warp[ch][cw] + 1
print(warp[D[0]-1][D[1]-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1
s = [input() for _ in range(H)]

def walk(h, w):
    q = deque([[h, w]])
    coord = []
    while q:
        y, x = q.popleft()
        for i, j in [(0,1), (0,-1), (1,0),(-1,0)]:
            if (y+i<0 or y+i>H-1) or (x+j<0 or x+j>W-1):
                continue
            if s[y+i][x+j] == '#':
                continue
            if m[y+i][x+j] != -1:
                continue
            q.append([y+i, x+j])
            m[y+i][x+j] = m[h][w]
            coord.append([y+i, x+j])
    return coord


def warp(h, w):
    coord = []
    v = m[h][w]
    h_s = max(0, h-2)
    h_e = min(H-1, h+2)
    w_s = max(0, w-2)
    w_e = min(W-1, w+2)
    for h1 in range(h_s, h_e+1):
        for w1 in range(w_s, w_e+1):
            if h==h1 and w==w1:
                continue
            if m[h1][w1] == -1 and s[h1][w1] != '#':
                m[h1][w1] = v + 1
                coord.append([h1, w1])
    return coord

    
m = [[-1] * W for _ in range(H)]
m[ch][cw] = 0
q = deque([[ch, cw]])
f = True
while q:
    y, x = q.popleft()
    coord = walk(y, x)
    co = []
    if f:
        coord.append([ch, cw])
    f = False
    for h, w in coord:
        co = warp(h, w)
    
    if len(co) == 0:
        break
    q.extend(co)

print(m[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
field = [input() for _ in range(H)]

wmap = [[-1] * W for _ in range(H)]
wmap[start[0]-1][start[1]-1] = 0

d = deque()
d.appendleft((start[1]-1,start[0]-1))

def flood():
    while len(d) > 0:
        posx, posy = d.pop()
        w = wmap[posy][posx]
        for x,y in [(posx-1, posy), (posx+1, posy), (posx, posy-1), (posx, posy+1)]:
            if 0 <= x < W and 0 <= y < H and field[y][x] == "." and wmap[y][x] == -1:
                wmap[y][x] = w
                d.appendleft((x,y))

def worp():
    init_v = 10**5
    for y in range(H):
        for x in range(W):
            if field[y][x] == "#":
                continue
            if wmap[y][x] >= 0:
                continue

            w = init_v
            for my in range(-2, 3):
                for mx in range(-2, 3):
                    px = x + mx
                    py = y + my
                    if 0 <= px < W and 0 <= py < H and field[py][px] == "." and wmap[py][px] >= 0:
                        w = min(w, wmap[py][px]+1)

            if w != init_v:
                wmap[y][x] = w
                d.append((x,y))

cnt = 0
while len(d) != 0 and wmap[goal[0]-1][goal[1]-1] == -1:
    flood()
    worp()
    cnt += 1

print(wmap[goal[0]-1][goal[1]-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    from time import time
    st = time()
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    while q:
        nh, nw = q.popleft()
        now = c[(nh, nw)]
        for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            mh += nh
            mw += nw
            if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                c[(mh, mw)] = now
                q.appendleft((mh, mw))
        for i in range(-2, 3):
            i += nh
            for j in range(-2, 3):
                j += nw
                if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and s[i][j] == ".":
                    c[(i, j)] = now + 1
                    q.append((i, j))
        if time() - st >= 1.8:
            print(333)
            return
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()