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: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for h in range(H):
        Sh =  list(input())
        S.append(Sh)

    que = {(Ch-1,Cw-1)}
    jump_que = set()
    goal = (Dh-1, Dw-1)
    searched=set()
    jump =0

    while(True):
        while(len(que)):
            tmp = que.pop()
            if tmp ==goal:
                print(jump)

                return

            searched.add(tmp)
            nxts=get_around(S,H,W,tmp[0],tmp[1], searched)
            # print(f'nxts: {nxts}')
            que=que|nxts
            jump_nxts = get_jump_around(S, H, W, tmp[0], tmp[1], searched)
            # print(f'jump_nxts: {jump_nxts}')
            jump_que = jump_que | jump_nxts
            # print(f'jump_que: {jump_que}')

        jump=jump+1
        que=jump_que
        jump_que = set()
        if len(que)==0:
            print('-1')
            return


def get_around(S,H,W, h,w, searched):
    hm = h-1
    hp =h+1
    wm = w-1
    wp= w+1
    nxt=set()
    if hm>=0 and S[hm][w]=='.' and (hm,w) not in searched:
        nxt.add((hm,w))

    if hp<H and S[hp][w]=='.'and (hp,w) not in searched:

        nxt.add((hp,w))
    if wm>=0 and S[h][wm]=='.'and (h,wm) not in searched:
        nxt.add((h,wm))

    if wp<W and S[h][wp]=='.'and (h,wp) not in searched:
        nxt.add((h,wp))
    return nxt

def get_jump_around(S,H,W, h,w, searched):
    hm = max(h-2,0)
    hp =min(h+2,H-1)
    wm = max(w-2,0)
    wp= min(w+2,W-1)
    nxt=set()
    # print(hm,hp,wm,wp)
    for h in range(hm,hp+1):
        for w in range(wm, wp + 1):
            if S[h][w]=='.' and (h,w) not in searched:
                nxt.add((h, w))

    return nxt


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output,out)

    def test_入力例_1(self):
        input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
    # すべての点を初期化
    wpCnt = [[int(10**10)] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = Cm-1
    sy = Cn-1

    que = deque([])
    que.append((sy, sx))
    wpCnt[sy][sx] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and wpCnt[nx][ny] > wpCnt[p[0]][p[1]]:
                # 移動できるならキューに入れ、優先的に処理
                wpCnt[nx][ny] = wpCnt[p[0]][p[1]]
                que.appendleft((nx, ny))

        # ワープ方向をループ
        for i in range(-2,3):
            for j in range(-2,3):
                # ワープした後の点を (nxw, nyw) とする
                nxw = p[0] + i
                nyw = p[1] + j

                # ワープが可能かの判定
                if 0 <= nxw < n and 0 <= nyw < m and maze[nxw][nyw] != "#" and 0 <= p[1] < m and 0 <= p[0] < n and wpCnt[nxw][nyw] > wpCnt[p[0]][p[1]] + 1 :
                    # ワープできるならキューに入れる
                    # print(nyw,nxw, p[0],p[1], i,j)
                    wpCnt[nxw][nyw] = wpCnt[p[0]][p[1]] + 1
                    que.append((nxw, nyw))
    return wpCnt

n, m = map(int, input().split())
Cn,Cm = map(int, input().split())
Dn,Dm = map(int, input().split())
maze = [list(input()) for _ in range(n)]

ans = bfs()

# print(ans)
if ans[Dn-1][Dm-1] == 10**10:
    print(-1)
else:
    print(ans[Dn-1][Dm-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and abs(i-2)+abs(j-2)==1 and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]])):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]+1)):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    H, W = read_ints()
    wiz = read_int_list()
    goal = read_int_list()
    grid = [read_str() for _ in range(H)]
    visit = [[False] * W for _ in range(H)]
    dist = [[-1] * W for _ in range(H)]
    
    que = deque([[wiz[0] - 1, wiz[1] - 1]])

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dx8 = [0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1]
    dy8 = [2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]
    cnt = 0

    while que or que2:
        que2 = deque()
        while que:
            y, x = que.popleft()
            dist[y][x] = cnt
            que2.append([y, x])

            if y == goal[0] - 1 and x == goal[1] - 1:
                print(dist[goal[0] - 1][goal[1] - 1])
                sys.exit()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != '#' and visit[ny][nx] == False:
                    que.append([ny, nx])
                    visit[ny][nx] = True
        
        cnt += 1
        while que2:
            y, x = que2.popleft()
            
            if y == goal[0] - 1 and x == goal[1] - 1:
                print(dist[goal[0] - 1][goal[1] - 1])
                sys.exit()

            for i in range(16):
                nx = x + dx8[i]
                ny = y + dy8[i]
                
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != '#' and visit[ny][nx] == False:
                    que.append([ny, nx])

    print(-1)


if __name__ ==  '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 遅すぎる！
import math
import sys


h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

x = [list(input()) for i in range(h)]

#print(x)
x[ch-1][cw-1]='a'

def tansaku():
    nu = 0
    while 1:
        nutta=0 # 塗ったマス
        for i in range(h):
            for j in range(w):
                if x[i][j] == 'a':
                    if i>0:
                        if x[i-1][j]=='.':
                            nutta += 1
                            x[i-1][j]='a'
                    if j>0:
                        if x[i][j-1]=='.':
                            nutta += 1
                            x[i][j-1]='a'
                    if i<h-1:
                        if x[i+1][j]=='.':
                            nutta += 1
                            x[i+1][j]='a'
                    if j<w-1:
                        if x[i][j+1]=='.':
                            nutta += 1
                            x[i][j+1]='a'
        if nutta==0:
            return nu
        else:
            nu += nutta

def warp():
    y = [[0 for j in range(w)] for i in range(h)]
    nu = 0
    for i in range(h):
        for j in range(w):
            if x[i][j] == 'a':
                for p in range(max(i-2,0),min(i+3,h)):
                    for q in range(max(j-2,0),min(j+3,w)):
                        if x[p][q] == '.':
                            y[p][q]='a'
                            #print("a",p,q)
                            nu += 1
    for i in range(h):
        for j in range(w):
            if y[i][j]=='a':
                x[i][j]='a'
                #print("b")
    return nu # これは塗った数よりは多いがnuが1なら0ではない


answer = 0
while(1):
    #print(x,ch,cw,dh,dw)
    nurioe = tansaku()
    #print(x,nurioe)
    if x[dh-1][dw-1]=='a':
        print(answer)
        break
    nurioe = warp()
    answer += 1
    #print(x,nurioe)
    if nurioe == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]=="#":
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]=="#":
				for xxx in range(-2,3):
					for yyy in range(-2,3):
						if S[x+xxx][y+yyy]==".":
							S[x+xxx][y+yyy]=d+1
							heapq.heappush(Q,[d+1,x+xxx,y+yyy])
				break






	#print(S[2:-2])

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


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
from queue import deque

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = deque([(0, 0, Si-1, Sj-1)])
#heapify(que)
visited = set()

while que:
    count, priority, r, c = que.popleft()#heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    if (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        que.appendleft((count, priority+1, r+td, c+lr))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            que.append((count+1, priority+1, r+ud, c+lr))
print('-1')

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

A = 10**18
B = 10**9

dx = []
dy = []
cost = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0: continue
        elif (i, j) in [(-1,0),(1,0),(0,-1),(0,1)]:
            dx.append(i)
            dy.append(j)
            cost.append(0)
        else:
            dx.append(i)
            dy.append(j)
            cost.append(1)

d[(ch-1) * w + (cw-1)] = 0
q = [(ch-1)*A + (cw-1)*B + 0]
use = [0] * (h * w)

for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    tmp = curh * w + curw
    if d[tmp] < cnt or use[tmp]: continue
    d[tmp] = cnt
    use[tmp] = 1

    for i in range(24):
        nh = curh + dx[i]
        nw = curw + dy[i]
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt + cost[i]:
            d[nh * w + nw] = cnt + cost[i]
            use[nh * w + nw] = 0
            q.append(nh*A + nw*B + cnt + cost[i])

gh -= 1
gw -= 1
if d[gh*w + gw] == INF: print(-1)
else: print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(w+2) for _ in range(h+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.popleft()

    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


for y in range(h):
    for x in range(w):
        if s[y][x]=='.':
            s[y][x]=10000000


s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
while que:
    y,x=que.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]:
        if 0<=y+i<h and 0<=x+j<w:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if dist!='#':
                if i*i+j*j==1:
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])
                elif dist>s[y][x]+1:
                    s[nexty][nextx]=s[y][x]+1
                    que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])