AtCoder Beginner Contest 176 - Wizard in Maze

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-----
4 4
1 1
4 4
..#.
..#.
.#..
.#..

-----Sample Output-----
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.

Source: atcoder | Difficulty: MEDIUM


Solutions:
from collections import *
I = 9 ** 9
((h, w), (s, t), (f, g)) = eval('map(int,input().split()),' * 3)
m = [input() for _ in range(h)]
d = [w * [I] for _ in m]
q = deque([(s - 1, t - 1, 1)])
while q:
	(y, x, c) = q.popleft()
	if d[y][x] < I:
		continue
	d[y][x] = c
	for i in range(y - 2, y + 3):
		for j in range(x - 2, x + 3):
			if h > i > -1 < j < w < I == d[i][j] != m[i][j] > '#':
				if abs(y - i) + abs(x - j) < 2:
					q.appendleft((i, j, c))
				else:
					q.append((i, j, c + 1))
print(d[f - 1][g - 1] % I - 1)


import heapq
(H, W) = map(int, input().split())
(sy, sx) = map(lambda x: int(x) - 1, input().split())
(ty, tx) = map(lambda x: int(x) - 1, input().split())
(s, t) = (sy * W + sx, ty * W + tx)
graph = [input() for _ in range(H)]
INF = 1 << 30
dist = [INF] * (H * W)
que = []

def push(v, d):
	if dist[v] <= d:
		return
	dist[v] = d
	heapq.heappush(que, (d, v))

def move(ny, nx, d):
	if ny < 0 or ny >= H or nx < 0 or (nx >= W):
		return
	if graph[ny][nx] == '.':
		push(ny * W + nx, d)
push(s, 0)
while que:
	(d, v) = heapq.heappop(que)
	if d > dist[v]:
		continue
	if v == t:
		break
	(y, x) = divmod(v, W)
	for dy in range(-2, 3):
		for dx in range(-2, 3):
			move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))
if dist[t] == INF:
	print(-1)
else:
	print(dist[t])


dhw = [(1, 0), (0, -1), (0, 1), (-1, 0), (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)]
(H, W) = map(int, input().split())
(sh, sw) = map(lambda x: int(x) - 1, input().split())
(eh, ew) = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]
dst = [[-1] * W for _ in range(H)]
from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
	(h, w, d) = dq.popleft()
	if 0 <= h < H and 0 <= w < W and (dst[h][w] < 0) and (S[h][w] != '#'):
		dst[h][w] = d
		for (dh, dw) in dhw[:4]:
			dq.appendleft((h + dh, w + dw, d))
		for (dh, dw) in dhw[4:]:
			dq.append((h + dh, w + dw, d + 1))
print(dst[eh][ew])


from collections import deque
(h, w) = map(int, input().split())
(i0, j0) = map(lambda x: int(x) - 1, input().split())
(i1, j1) = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
	(i, j, cnt) = Q.popleft()
	if D[i][j] != -1:
		continue
	D[i][j] = cnt
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if 0 <= i + di < h and 0 <= j + dj < w and (S[i + di][j + dj] == '.') and (D[i + di][j + dj] == -1):
				if abs(di) + abs(dj) == 1:
					Q.appendleft((i + di, j + dj, cnt))
				else:
					Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])


(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = []
for i in range(h):
	s.append([c for c in input()])
queue = [[(ch - 1, cw - 1)], []]
dist = 0
while len(queue[0]) > 0:
	while len(queue[0]) > 0:
		(y, x) = queue[0].pop()
		if s[y][x] != '.':
			continue
		s[y][x] = dist
		for vy in range(-2, 3):
			for vx in range(-2, 3):
				if 0 <= y + vy < h and 0 <= x + vx < w and (s[y + vy][x + vx] == '.'):
					cost = 0 if abs(vx) + abs(vy) <= 1 else 1
					queue[cost].append((y + vy, x + vx))
	dist += 1
	queue = [queue[1], queue[0]]
dist = s[dh - 1][dw - 1]
print(dist if dist != '.' else -1)


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


from collections import deque
import sys
(h, w) = map(int, input().split())
(sy, sx) = map(lambda x: int(x) - 1, input().split())
(gy, gx) = map(lambda x: int(x) - 1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(h)]
d = deque([(sy, sx)])
cur = 1
while True:
	visited = set()
	while d:
		(y, x) = d.pop()
		visited.add((y, x))
		S[y][x] = cur
		if (y, x) == (gy, gx):
			print(cur - 1)
			sys.exit()
		for (dyi, dxi) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			if 0 <= y + dyi < h and 0 <= x + dxi < w and (S[y + dyi][x + dxi] == 0):
				d.append((y + dyi, x + dxi))
	for (y, x) in visited:
		for dyi in range(-2, 3):
			for dxi in range(-2, 3):
				if 0 <= y + dyi < h and 0 <= x + dxi < w and (S[y + dyi][x + dxi] == 0):
					d.append((y + dyi, x + dxi))
	if not d:
		print(-1)
		sys.exit()
	cur += 1


from collections import deque
import sys
sys.setrecursionlimit(1000000)
(H, W) = map(int, input().split())
(curX, curY) = map(int, input().split())
curX -= 1
curY -= 1
(goalX, goalY) = map(int, input().split())
goalX -= 1
goalY -= 1
graph = [list(input()) for _ in range(H)]
q = deque([(curX, curY)])
dist = [[float('inf')] * W for _ in range(H)]
dist[curX][curY] = 0
while q:
	(r, c) = q.popleft()
	if r == goalX and c == goalY:
		break
	hop = dist[r][c]
	for (x, y) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		(nr, nc) = (r + x, c + y)
		if 0 <= nr < H and 0 <= nc < W and (graph[nr][nc] != '#') and (dist[nr][nc] > hop):
			dist[nr][nc] = hop
			q.appendleft((nr, nc))
	for i in range(-2, 3):
		for j in range(-2, 3):
			(nr, nc) = (r + i, c + j)
			if 0 <= nr < H and 0 <= nc < W and (graph[nr][nc] != '#') and (dist[nr][nc] > hop + 1):
				dist[nr][nc] = hop + 1
				q.append((nr, nc))
ans = dist[goalX][goalY]
if ans == float('inf'):
	print(-1)
else:
	print(ans)


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 _ in range(H)]
que = deque([(0, Ch - 1, Cw - 1)])
adjecents = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while que:
	(step, h, w) = que.popleft()
	if h == Dh - 1 and w == Dw - 1:
		print(step)
		exit()
	if maze[h][w] == '#':
		continue
	else:
		maze[h][w] = '#'
		for (a, b) in adjecents:
			x = h + a
			y = w + b
			if 0 <= x < H and 0 <= y < W:
				if maze[x][y] == '.':
					que.appendleft((step, x, y))
				else:
					for i in range(-2, 3):
						for j in range(-2, 3):
							x = h + i
							y = w + j
							if 0 <= x < H and 0 <= y < W and (maze[x][y] == '.'):
								que.append((step + 1, x, y))
print(-1)


(h, w) = list(map(int, input().split()))
(sx, sy) = list(map(int, input().split()))
(gx, gy) = list(map(int, input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1
sy -= 1
gx -= 1
gy -= 1
mx = [0, 1, 0, -1]
my = [1, 0, -1, 0]
mazemap = [[10 ** 9] * w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx, sy, 0])
while q or nq:
	(x, y, z) = q.popleft() if q else nq.popleft()
	if x == gx and y == gy:
		ans = z
		break
	for i in range(4):
		nx = x + mx[i]
		ny = y + my[i]
		if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] != '#') and (mazemap[nx][ny] > z):
			q.append([nx, ny, z])
			mazemap[nx][ny] = z
		for i in range(-2, 3):
			for j in range(-2, 3):
				nx = x + i
				ny = y + j
				if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] != '#') and (mazemap[nx][ny] > z + 1):
					nq.append([nx, ny, z + 1])
					mazemap[nx][ny] = z + 1
else:
	ans = -1
print(ans)


import heapq
INF = 10000000.0
(H, W) = map(int, input().split())
(sx, sy) = map(int, input().split())
(dh, dw) = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]

def dijkstra(sx, sy):
	D = [[INF] * W for _ in range(H)]
	D[sx][sy] = 0
	PQ = [(0, (sx, sy))]
	heapq.heapify(PQ)
	while PQ:
		(_, (ux, uy)) = heapq.heappop(PQ)
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				(xx, yy) = (ux + dx, uy + dy)
				if 0 <= xx < H and 0 <= yy < W and (S[xx][yy] == '.'):
					is_not_neighbor = int(abs(dx) + abs(dy) != 1)
					if D[ux][uy] + is_not_neighbor < D[xx][yy]:
						D[xx][yy] = D[ux][uy] + is_not_neighbor
						heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
	return D
D = dijkstra(sx, sy)
if D[dh - 1][dw - 1] >= INF:
	print(-1)
else:
	print(D[dh - 1][dw - 1])


def main():
	(H, W) = list(map(int, input().split()))
	(y, x) = list(map(int, input().split()))
	start = (x + 1, y + 1)
	(y, x) = list(map(int, input().split()))
	goal = (x + 1, y + 1)
	dist_table = [[-2] * (W + 4)]
	dist_table.append([-2] * (W + 4))
	for _ in range(H):
		row = '##' + input() + '##'
		row = [-1 if c == '.' else -2 for c in row]
		dist_table.append(row)
	dist_table.append([-2] * (W + 4))
	dist_table.append([-2] * (W + 4))
	(sx, sy) = start
	dist_table[sy][sx] = 0
	move1 = ((-1, 0), (1, 0), (0, 1), (0, -1))
	move2 = ((-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))
	queue1 = [start]
	queue2 = []
	while queue1:
		(now_x, now_y) = queue1.pop()
		if (now_x, now_y) == goal:
			break
		queue2.append((now_x, now_y))
		dist = dist_table[now_y][now_x]
		for (dx, dy) in move1:
			(tx, ty) = (now_x + dx, now_y + dy)
			if dist_table[ty][tx] == -1:
				dist_table[ty][tx] = dist
				queue1.append((tx, ty))
		if len(queue1) == 0:
			while queue2:
				(now_x, now_y) = queue2.pop()
				dist = dist_table[now_y][now_x]
				for (dx, dy) in move2:
					(tx, ty) = (now_x + dx, now_y + dy)
					if dist_table[ty][tx] == -1:
						dist_table[ty][tx] = dist + 1
						queue1.append((tx, ty))
	(gx, gy) = goal
	print(dist_table[gy][gx])

def __starting_point():
	main()
__starting_point()


import sys
from collections import deque
(H, W) = map(int, input().split())
(si, sj) = [int(x) - 1 for x in input().split()]
(ti, tj) = [int(x) - 1 for x in input().split()]
A = list(sys.stdin)
dirs = [-2, -1, 0, 1, 2]
dist = [[float('inf')] * W for _ in range(H)]
dist[si][sj] = 0
dq = deque()
dq.append((0, si, sj))
ok = False
while dq:
	(k, i, j) = dq.popleft()
	if i == ti and j == tj:
		ok = True
		break
	for di in dirs:
		for dj in dirs:
			if di == dj == 0:
				continue
			(ni, nj) = (i + di, j + dj)
			if not (0 <= ni < H and 0 <= nj < W):
				continue
			if A[ni][nj] == '#':
				continue
			if abs(di) + abs(dj) == 1:
				append = dq.appendleft
				nk = k
			else:
				append = dq.append
				nk = k + 1
			if k >= dist[ni][nj]:
				continue
			dist[ni][nj] = nk
			append((nk, ni, nj))
if ok:
	ans = dist[ti][tj]
else:
	ans = -1
print(ans)


from _collections import deque
(h, w) = map(int, input().split())
(c_h, c_w) = map(int, input().split())
(d_h, d_w) = map(int, input().split())
M = [input() for i in range(h)]
V = [[10 ** 9] * w for i in range(h)]
q = deque([[0, c_h - 1, c_w - 1]])
while q:
	(warp, x, y) = q.popleft()
	if V[x][y] != 10 ** 9:
		continue
	V[x][y] = warp
	if x == d_h - 1 and y == d_w - 1:
		break
	for px in range(-2, 3):
		for py in range(-2, 3):
			if 0 <= x + px < h and 0 <= y + py < w:
				if px == 0 and py == 0:
					continue
				if M[x + px][y + py] == '#':
					continue
				if abs(px) + abs(py) <= 1:
					q.appendleft([warp, x + px, y + py])
				else:
					q.append([warp + 1, x + px, y + py])
if V[d_h - 1][d_w - 1] == 10 ** 9:
	print(-1)
else:
	print(V[d_h - 1][d_w - 1])


from collections import deque
from itertools import product

def bfs(x, y):
	dist = [[10 ** 9] * w for _ in range(h)]
	dist[y][x] = 0
	que = deque([(x, y)])
	near = list(product(range(-2, 3), repeat=2))
	while len(que) > 0:
		(x, y) = que.popleft()
		if (x, y) == (Dw - 1, Dh - 1):
			return dist[y][x]
		for (dx, dy) in near:
			cnt = abs(dx) + abs(dy) >= 2
			(i, j) = (x + dx, y + dy)
			if 0 <= i < w and 0 <= j < h and (dist[j][i] > dist[y][x] + cnt) and (s[j][i] == '.'):
				dist[j][i] = dist[y][x] + cnt
				if cnt == 0:
					que.appendleft((i, j))
				elif cnt == 1:
					que.append((i, j))
	return -1
(h, w) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
s = [input() for _ in range(h)]
print(bfs(Cw - 1, Ch - 1))


from collections import deque
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
S = [input() for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
P = [[float('inf')] * W for _ in range(H)]
a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque()
q.append((Ch, Cw, 0))
while q:
	dq = deque()
	(hh, ww, d) = q.popleft()
	if type(P[hh][ww]) is int:
		continue
	dq.append((hh, ww))
	P[hh][ww] = d
	V = []
	while dq:
		(h, w) = dq.popleft()
		V.append((h, w))
		for n in a:
			nh = h + n[0]
			nw = w + n[1]
			if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (type(P[nh][nw]) is float):
				P[nh][nw] = min(P[nh][nw], P[h][w])
				dq.append((nh, nw))
	for (h, w) in V:
		for x in range(-2, 3):
			for y in range(-2, 3):
				nh = h + x
				nw = w + y
				if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (type(P[nh][nw]) is float):
					q.append((nh, nw, d + 1))
ans = P[Dh][Dw]
print(ans if type(ans) is int else -1)


from collections import deque
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
(Ch, Cw, Dh, Dw) = (Ch - 1, Cw - 1, Dh - 1, Dw - 1)
maze = [input() for _ in range(H)]
visit = [[-1] * W for _ in range(H)]
visit[Ch][Cw] = 0
DQ = deque([[Ch, Cw]])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while DQ:
	(px, py) = DQ.popleft()
	if px == Dh and py == Dw:
		print(visit[px][py])
		exit()
	for i in range(4):
		nx = px + dx[i]
		ny = py + dy[i]
		if 0 <= nx <= H - 1 and 0 <= ny <= W - 1 and (maze[nx][ny] == '.') and (visit[nx][ny] > visit[px][py] or visit[nx][ny] == -1):
			visit[nx][ny] = visit[px][py]
			DQ.appendleft([nx, ny])
	for i in range(-2, 3):
		for j in range(-2, 3):
			if i == j == 0:
				continue
			nx = px + i
			ny = py + j
			if 0 <= nx <= H - 1 and 0 <= ny <= W - 1 and (maze[nx][ny] == '.') and (visit[nx][ny] == -1):
				visit[nx][ny] = visit[px][py] + 1
				DQ.append([nx, ny])
print(-1)


from collections import deque
(H, W) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
field = [list(input()) for _ in range(H)]
(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1)
Walk = [[1, 0], [0, 1], [-1, 0], [0, -1]]
Warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3)]
dist = [[-1] * W for _ in range(H)]
que = deque()
dist[sy][sx] = 0
que.append([sy, sx])
while que:
	(y, x) = que.popleft()
	for walk in Walk:
		(nx, ny) = (x + walk[0], y + walk[1])
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if field[ny][nx] == '#':
			continue
		if dist[ny][nx] != dist[y][x]:
			dist[ny][nx] = dist[y][x]
			que.appendleft([ny, nx])
	for warp in Warp:
		(nx, ny) = (x + warp[0], y + warp[1])
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if field[ny][nx] == '#':
			continue
		if dist[ny][nx] == -1:
			dist[ny][nx] = dist[y][x] + 1
			que.append([ny, nx])
print(dist[gy][gx])


from collections import deque
(H, W) = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
F = [['#'] * (W + 4)]
F += [['#'] * (W + 4)]
F += [['#'] + ['#'] + list(input()) + ['#'] + ['#'] for _ in range(H)]
F += [['#'] * (W + 4)]
F += [['#'] * (W + 4)]
res = [[-1] * (W + 4) for _ in range(H + 4)]
Q = deque()
Q2 = deque()
Q.append([C[0] + 1, C[1] + 1])
Q2.append([C[0] + 1, C[1] + 1])
f_n = True
nd = ((0, 1), (0, -1), (1, 0), (-1, 0))
bnum = 0
while f_n:
	f_n = False
	while len(Q) > 0:
		(x, y) = Q.popleft()
		Q2.append([x, y])
		for (dx, dy) in nd:
			xx = x + dx
			yy = y + dy
			if F[xx][yy] == '.' and res[xx][yy] == -1:
				Q.append([xx, yy])
				res[xx][yy] = bnum
	bnum += 1
	while len(Q2) > 0:
		(x, y) = Q2.popleft()
		for i in range(-2, 3):
			for j in range(-2, 3):
				xx = x + i
				yy = y + j
				if F[xx][yy] == '.' and res[xx][yy] == -1:
					Q.append([xx, yy])
					res[xx][yy] = bnum
					f_n = True
print(res[D[0] + 1][D[1] + 1])


from collections import deque
from itertools import product

def main():
	(h, w) = list(map(int, input().split()))
	c = tuple([int(x) + 1 for x in input().split()])
	d = tuple([int(x) + 1 for x in input().split()])
	s = ['#' * (w + 4)] * 2 + [f'##{input()}##' for _ in range(h)] + ['#' * (w + 4)] * 2
	move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
	move_b_area = [(i, j) for (i, j) in product(list(range(-2, 3)), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]
	cost = [[float('inf')] * (w + 4) for _ in range(h + 4)]
	cost[c[0]][c[1]] = 0
	yet = deque([(c[0], c[1], 0)])
	done = deque()
	while yet:
		(y, x, m) = yet.popleft()
		done.append((y, x, m))
		for (dx, dy) in move_a_area:
			(hh, ww) = (y + dy, x + dx)
			if s[hh][ww] == '#' or cost[hh][ww] <= m:
				continue
			cost[hh][ww] = m
			yet.append((hh, ww, m))
		if not yet:
			while done:
				(y, x, m) = done.popleft()
				for (dx, dy) in move_b_area:
					(hh, ww) = (y + dy, x + dx)
					if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
						continue
					cost[hh][ww] = m + 1
					yet.append((hh, ww, m + 1))
	print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)

def __starting_point():
	main()
__starting_point()


from collections import deque

def main():
	(h, w) = map(int, input().split())
	cs = list(map(int, input().split()))
	ds = list(map(int, input().split()))
	S = [[s for s in input()] for _ in range(h)]
	curq = deque()
	nexq = deque([(cs[0] - 1, cs[1] - 1)])
	l = 0
	while len(nexq) > 0:
		(curq, nexq) = (nexq, deque())
		while len(curq) > 0:
			(y, x) = curq.popleft()
			if S[y][x] != '.':
				continue
			S[y][x] = l
			for dy in range(-2, 3):
				for dx in range(-2, 3):
					if 0 <= y + dy < h and 0 <= x + dx < w and (S[y + dy][x + dx] == '.'):
						if abs(dx) + abs(dy) < 2:
							curq.append((y + dy, x + dx))
						else:
							nexq.append((y + dy, x + dx))
		l += 1
	ans = S[ds[0] - 1][ds[1] - 1]
	print(ans if ans != '.' else -1)
main()


from collections import deque
import sys
INF = 10000000
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
S = [input() for _ in range(H)]
C = [[INF] * W for _ in range(H)]
C[Ch - 1][Cw - 1] = 0
que = deque([(Ch, Cw)])
now = set()
tmp = 0
while True:
	while len(que) > 0:
		(i, j) = que.popleft()
		now.add((i, j))
		for (h, w) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
			if 1 <= h <= H and 1 <= w <= W and (S[h - 1][w - 1] == '.') and (C[h - 1][w - 1] > tmp):
				C[h - 1][w - 1] = tmp
				que.append((h, w))
	for (i, j) in now:
		for h in range(i - 2, i + 3):
			for w in range(j - 2, j + 3):
				if 1 <= h <= H and 1 <= w <= W and (S[h - 1][w - 1] == '.') and (C[h - 1][w - 1] > tmp + 1):
					C[h - 1][w - 1] = tmp + 1
					que.append((h, w))
	now = set()
	tmp += 1
	if C[Dh - 1][Dw - 1] != INF:
		print(C[Dh - 1][Dw - 1])
		break
	if len(que) == 0:
		print(-1)
		break


from collections import deque

def solve():
	(h, w) = list(map(int, input().split()))
	(ch, cw) = list(map(int, input().split()))
	(Dh, Dw) = list(map(int, input().split()))
	M = ['##' + input() + '##' for _ in range(h)]
	for i in range(2):
		M.insert(0, '#' * (w + 4))
		M.append('#' * (w + 4))
	INF = float('inf')
	cost = [[INF for _ in range(w + 4)] for _ in range(h + 4)]
	cost0 = deque()
	ans = -1
	cost0.append((ch + 1, cw + 1, 0))
	cost[ch + 1][cw + 1] = 0
	move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move]
	cost1 = deque()
	while cost0:
		(h, w, c) = cost0.popleft()
		cost1.append((h, w, c))
		for (i, j) in move:
			dh = h + i
			dw = w + j
			if M[dh][dw] == '.' and c < cost[dh][dw]:
				cost[dh][dw] = c
				cost0.appendleft((dh, dw, cost[dh][dw]))
		if len(cost0) == 0:
			while cost1:
				(h, w, c) = cost1.popleft()
				for (i, j) in warp:
					dh = h + i
					dw = w + j
					if M[dh][dw] == '.' and c + 1 < cost[dh][dw]:
						cost[dh][dw] = c + 1
						cost0.append((dh, dw, cost[dh][dw]))
		if cost[Dh + 1][Dw + 1] != INF:
			ans = cost[Dh + 1][Dw + 1]
	print(ans)

def __starting_point():
	solve()
__starting_point()


def main():
	from collections import deque
	import sys
	input = sys.stdin.readline
	(h, w) = list(map(int, input().split()))
	(ch, cw) = list(map(int, input().split()))
	(dh, dw) = list(map(int, input().split()))
	maze = ['#' * (w + 4)]
	maze.append('#' * (w + 4))
	for _ in range(h):
		maze.append('##' + input()[:-1] + '##')
	maze.append('#' * (w + 4))
	maze.append('#' * (w + 4))
	visited = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if maze[i][j] == '#':
				visited[i][j] = -2
	ch += 1
	cw += 1
	dh += 1
	dw += 1
	visited[ch][cw] = 0
	walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	telepo = [[i, j] for i in range(-2, 3) for j in range(-2, 3)]
	q_walk = deque([[ch, cw]])
	q_telepo = deque([])
	while q_walk:
		(yw, xw) = q_walk.popleft()
		q_telepo.append([yw, xw])
		for (i, j) in walk:
			(ny, nx) = (yw + i, xw + j)
			if visited[ny][nx] == -1:
				visited[ny][nx] = visited[yw][xw]
				q_walk.append([ny, nx])
		if len(q_walk) == 0:
			while q_telepo:
				(yt, xt) = q_telepo.popleft()
				for (i, j) in telepo:
					(my, mx) = (yt + i, xt + j)
					if visited[my][mx] == -1:
						visited[my][mx] = visited[yt][xt] + 1
						q_walk.append([my, mx])
	print(visited[dh][dw])

def __starting_point():
	main()
__starting_point()


import collections, itertools
(h, w) = map(int, input().split())
(ch, cw) = tuple((int(s) - 1 for s in input().split()))
(dh, dw) = tuple((int(s) - 1 for s in input().split()))
s = [input() for _ in range(h)]
q = collections.deque()
q.append((ch, cw, 0))
score = [[float('inf')] * w for _ in range(h)]
score[ch][cw] = 0
while q:
	(x, y, p) = q.popleft()
	for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < h and 0 <= ny < w and (s[nx][ny] == '.') and (p < score[nx][ny]):
			score[nx][ny] = p
			q.appendleft((nx, ny, p))
	for (dx, dy) in itertools.product(range(-2, 3), repeat=2):
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < h and 0 <= ny < w and (s[nx][ny] == '.') and (p + 1 < score[nx][ny]):
			score[nx][ny] = p + 1
			q.append((nx, ny, p + 1))
if score[dh][dw] == float('inf'):
	print(-1)
else:
	print(score[dh][dw])


import sys
readline = sys.stdin.buffer.readline

def readstr():
	return readline().rstrip().decode()

def readints():
	return list(map(int, readline().split()))
from collections import deque
(h, w) = readints()
start = readints()
start = (start[0] - 1) * w + start[1] - 1
goal = readints()
goal = (goal[0] - 1) * w + goal[1] - 1
maze = [readstr() for i in range(h)]
dist = [10 ** 10] * (h * w)
dq = deque()
dq.append(start)
dist[start] = 0
while dq:
	p = dq.popleft()
	y = p // w
	x = p % w
	for dy in range(-2, 3):
		for dx in range(-2, 3):
			if 0 <= y + dy < h and 0 <= x + dx < w and (maze[y + dy][x + dx] == '.'):
				q = (y + dy) * w + x + dx
				if abs(dy) + abs(dx) == 1:
					if dist[q] > dist[p]:
						dq.appendleft(q)
						dist[q] = dist[p]
				elif dist[q] > dist[p] + 1:
					dq.append(q)
					dist[q] = dist[p] + 1
print(-1 if dist[goal] == 10 ** 10 else dist[goal])


from collections import deque

def solve(H, W, CH, CW, DH, DW):
	S = [input() for _ in range(H)]
	S = ['##{}##'.format(row) for row in S]
	S.insert(0, '##{}##'.format('#' * W))
	S.insert(0, '##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	MAX_COST = 10 ** 9
	Cost = [[MAX_COST for _ in range(W + 4)] for _ in range(H + 4)]
	ans = -1
	cost0 = deque()
	cost0.append((CH + 1, CW + 1, 0))
	Cost[CH + 1][CW + 1] = 0
	walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
	cost1 = deque()
	while cost0:
		(h, w, c) = cost0.popleft()
		cost1.append((h, w, c))
		for (i, j) in walk:
			dh = h + i
			dw = w + j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				cost0.appendleft((dh, dw, Cost[dh][dw]))
		if len(cost0) == 0:
			while cost1:
				(h, w, c) = cost1.popleft()
				for (i, j) in warp:
					dh = h + i
					dw = w + j
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh, dw, Cost[dh][dw]))
	if Cost[DH + 1][DW + 1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH + 1][DW + 1])

def __starting_point():
	(H, W) = list(map(int, input().split()))
	(CH, CW) = list(map(int, input().split()))
	(DH, DW) = list(map(int, input().split()))
	solve(H, W, CH, CW, DH, DW)
__starting_point()


from collections import *

def main():
	(H, W) = map(int, input().split())
	(ch, cw) = map(int, input().split())
	(dh, dw) = map(int, input().split())
	s = ['#' * (W + 4)]
	s.append('#' * (W + 4))
	for i in range(H):
		s.append('##' + input() + '##')
	s.append('#' * (W + 4))
	s.append('#' * (W + 4))
	ans = [[-1] * (W + 4) for _ in range(H + 4)]
	for i in range(H + 4):
		for j in range(W + 4):
			if s[i][j] == '#':
				ans[i][j] = -2
	ch += 1
	cw += 1
	dh += 1
	dw += 1
	ans[ch][cw] = 0
	move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
	mylist = deque([[ch, cw]])
	mylist2 = deque([])
	while len(mylist) > 0:
		(x, y) = mylist.popleft()
		mylist2.append([x, y])
		for (p, q) in move:
			(v1, v2) = (x + p, y + q)
			if ans[v1][v2] == -1:
				mylist.append([v1, v2])
				ans[v1][v2] = ans[x][y]
		if len(mylist) == 0:
			while len(mylist2) > 0:
				(x2, y2) = mylist2.popleft()
				for (v1, v2) in magic:
					(i, j) = (x2 + v1, y2 + v2)
					if ans[i][j] == -1:
						ans[i][j] = ans[x2][y2] + 1
						mylist.append([i, j])
	print(ans[dh][dw])

def __starting_point():
	main()
__starting_point()


import zlib, base64
exec(zlib.decompress(base64.b85decode('c-l2k%Wi`(5WMphj;e}XSdx$`mw@vl76$_+EaG9nDM`P+j+!2JMw*?~Xtr6VK~z)Uo67Mtu7U?UEiMY6r40#IavmGHp)}vRhj7pqcyz?0y*t4DYJ2vK6h>bd3{=Y>wh;Z9;q4-oq(!v7Of6zC%i7F$0}9q8CFkde1qNHoy%F;z5KnqgCFi}JEMOqG5w&_2>QUrJzZK222rYONiym(VPG`JmDy2Rg&dG`Nr^k$?j-Od4%lMJKk7bp$SH31`-sRg)4vGua71!`1+)2>o3L4`Vm6)G)K3!XD#u|XBqslk@S9;U9w;HGD``E>Q1Zvgzmg?pKe*wqdW>^')))


import sys
input = lambda : sys.stdin.readline().rstrip()
from heapq import *
(H, W) = map(int, input().split())
m1 = lambda s: int(s) - 1
(sy, sx) = map(m1, input().split())
(fy, fx) = map(m1, input().split())
G = [list(input()) for _ in range(H)]
D = [[10 ** 18] * W for _ in range(H)]
D[sy][sx] = 0
Q = [(0, sx, sy)]
while Q:
	(d, x, y) = heappop(Q)
	if D[y][x] < d:
		continue
	if (x, y) == (fx, fy):
		print(d)
		break
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			nx = x + dx
			ny = y + dy
			if nx < 0 or ny < 0 or nx >= W or (ny >= H) or (G[ny][nx] == '#'):
				continue
			nd = d + (0 if abs(dx) + abs(dy) == 1 else 1)
			if nd >= D[ny][nx]:
				continue
			D[ny][nx] = nd
			heappush(Q, (nd, nx, ny))
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
d = deque()
d.append([ch - 1, cw - 1])
dist = [[float('inf')] * w for _ in range(h)]
dist[ch - 1][cw - 1] = 0
while d:
	(x, y) = d.popleft()
	for i in range(-2, 3):
		for j in range(-2, 3):
			if 0 <= x + i < h and 0 <= y + j < w and (s[x + i][y + j] == '.'):
				if i == 0 and j == 0:
					continue
				elif i == 1 and j == 0 or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 0 and j == -1):
					if dist[x + i][y + j] > dist[x][y]:
						dist[x + i][y + j] = dist[x][y]
						d.appendleft([x + i, y + j])
				elif dist[x + i][y + j] > dist[x][y] + 1:
					dist[x + i][y + j] = dist[x][y] + 1
					d.append([x + i, y + j])
print(dist[dh - 1][dw - 1] if dist[dh - 1][dw - 1] != float('inf') else -1)


from collections import deque
import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
(CH, CW) = map(lambda x: int(x) - 1, input().split())
(DH, DW) = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
v = [[False] * W for _ in range(H)]
dq = deque([(0, CH, CW)])
while dq:
	(d, h, w) = dq.popleft()
	if (h, w) == (DH, DW):
		print(d)
		exit()
	if v[h][w]:
		continue
	v[h][w] = True
	for (mh, mw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		(nh, nw) = (mh + h, mw + w)
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.'):
			dq.appendleft([d, nh, nw])
	for mh in range(-2, 3):
		for mw in range(-2, 3):
			if mh == mw == 0:
				continue
			(nh, nw) = (mh + h, mw + w)
			if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (not v[nh][nw]):
				dq.append([d + 1, nh, nw])
print(-1)


INF = 10 ** 6
f = lambda : map(int, input().split())
(h, w) = f()
(ch, cw) = f()
ch -= 1
cw -= 1
(dh, dw) = f()
dh -= 1
dw -= 1
g = [input() for _ in range(h)]
from collections import *

def grid_01_bfs(x, y):
	d = [[INF] * w for _ in range(h)]
	d[x][y] = 0
	q = deque([(0, x, y)])
	while q:
		(td, tx, ty) = q.popleft()
		if d[tx][ty] < td:
			continue
		for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			(nx, ny) = (tx + dx, ty + dy)
			if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] > td):
				d[nx][ny] = td
				q.appendleft((d[nx][ny], nx, ny))
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				(nx, ny) = (tx + dx, ty + dy)
				if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] > td + 1):
					d[nx][ny] = td + 1
					q.append((d[nx][ny], nx, ny))
	return d
a = grid_01_bfs(ch, cw)[dh][dw]
print([-1, a][a < INF])


from collections import deque
(H, W) = map(int, input().split())
c = tuple((int(x) + 1 for x in input().split()))
d = [int(x) + 1 for x in input().split()]
maze = [[-1] * (W + 4), [-1] * (W + 4)]
for i in range(H):
	temp = []
	s0 = input()
	s0 = '11' + s0.replace('.', '0').replace('#', '1') + '11'
	for (j, s) in enumerate(s0):
		temp.append(-int(s))
	maze.append(temp)
maze.append([-1] * (W + 4))
maze.append([-1] * (W + 4))

def check55(i, j):
	cset = {(ii, jj) for ii in range(i - 2, i + 3) for jj in range(j - 2, j + 3) if maze[ii][jj] == 0}
	cset = cset - {(i - 1, j), (i, j), (i + 1, j), (i, j - 1), (i, j + 1)}
	return cset

def check(i, j, delta):
	if delta[0] != 0:
		ii = i + 3 * delta[0]
		for jj in range(j - 2, j + 3):
			if maze[ii][jj] == 0:
				dset.add((ii, jj))
	else:
		jj = j + 3 * delta[1]
		for ii in range(i - 2, i + 3):
			if maze[ii][jj] == 0:
				dset.add((ii, jj))
	return
k = 1
tempbfs = deque([[c[0], c[1], k]])
flag = 0
while tempbfs:
	if flag == 1:
		break
	p = tempbfs.popleft()
	if maze[p[0]][p[1]] != 0:
		continue
	maze[p[0]][p[1]] = p[2]
	if p[0] == d[0] and p[1] == d[1]:
		flag = 1
		k = p[2]
		break
	temp = [(p[0], p[1])]
	dset = set()
	while temp:
		p0 = temp.pop()
		for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			y = p0[0] + delta[0]
			x = p0[1] + delta[1]
			if maze[y][x] != 0:
				continue
			maze[y][x] = p[2]
			if y == d[0] and x == d[1]:
				flag = 1
				k = p[2]
				break
			temp.append((y, x))
			check(p0[0], p0[1], delta)
	if flag == 1:
		break
	for l in dset:
		if maze[l[0]][l[1]] == 0:
			tempbfs.append([l[0], l[1], p[2] + 1])
	dset = check55(p[0], p[1])
	for l in dset:
		tempbfs.append([l[0], l[1], p[2] + 1])
print(k - 1 if flag else -1)


from collections import *
((h, w), (s, t), (f, g)) = eval('map(int,input().split()),' * 3)
d = eval('[-1]*w,input(),' * h)
q = deque([(s - 1, t - 1, 0)])
while q:
	(y, x, c) = q.pop()
	if d[y + y][x] < 0:
		for a in range(25):
			(a, b) = (a // 5 - 2, a % 5 - 2)
			i = a + y
			j = b + x
			d[y + y][x] = c
			h > i > -1 < j < w != d[i - ~i][j] > '#' != (abs(a) + abs(b) < 2 != q.append((i, j, c)), q.appendleft((i, j, c + 1)))
print(d[f + f - 2][g - 1])


from collections import deque
INF = 10 ** 10
dxdy = ((0, 1), (0, -1), (1, 0), (-1, 0))
(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)]
d = [[INF] * (w + 1) for _ in range(h + 1)]
d[ch][cw] = 0
q = deque([(ch, cw)])
while q:
	(y, x) = q.pop()
	for (dx, dy) in dxdy:
		if s[y + dy][x + dx] == '.' and d[y + dy][x + dx] > d[y][x]:
			d[y + dy][x + dx] = d[y][x]
			q.append((y + dy, x + dx))
	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 (d[y + i][x + j] > d[y][x] + 1):
				d[y + i][x + j] = d[y][x] + 1
				q.appendleft((y + i, x + j))
ans = d[dh][dw]
if ans == INF:
	print(-1)
else:
	print(ans)


import collections
(h, w) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
board = [['#'] * (w + 2)] + [list('#' + input() + '#') for _ in range(h)] + [['#'] * (w + 2)]
checked = [[False] * (w + 1) for _ in range(h + 1)]
checked[sy][sx] = True
q = collections.deque()
q.append((sy, sx))
ans = 0
while 1:
	cur_pos = []
	while len(q) != 0:
		(y, x) = q.popleft()
		cur_pos.append((y, x))
		for (dy, dx) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
			if 1 <= y + dy <= h and 1 <= x + dx <= w and (board[y + dy][x + dx] == '.') and (checked[y + dy][x + dx] == False):
				checked[y + dy][x + dx] = True
				q.append((y + dy, x + dx))
	if checked[gy][gx] == True:
		print(ans)
		exit()
	if len(cur_pos) == 0:
		print(-1)
		exit()
	ans += 1
	for (y, x) in cur_pos:
		for dy in range(-2, 3):
			for dx in range(-2, 3):
				if dy == 0 and dx == 0:
					continue
				if 1 <= y + dy <= h and 1 <= x + dx <= w and (board[y + dy][x + dx] == '.') and (checked[y + dy][x + dx] == False):
					checked[y + dy][x + dx] = True
					q.append((y + dy, x + dx))


import sys
input = sys.stdin.readline

def main():
	(h, w) = list(map(int, input().split()))
	(ch, cw) = list(map(int, input().split()))
	(dh, dw) = list(map(int, input().split()))
	ch += 1
	cw += 1
	dh += 1
	dw += 1
	s = ['#' * (w + 4)]
	s.append('#' * (w + 4))
	for i in range(h):
		s.append('##' + input()[:-1] + '##')
	s.append('#' * (w + 4))
	s.append('#' * (w + 4))
	ans = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if s[i][j] == '#':
				ans[i][j] = -2
	ans[ch][cw] = 0
	move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
	not_yet = [(ch, cw)]
	one_time = []
	while len(not_yet) > 0:
		(x, y) = not_yet.pop()
		one_time.append((x, y))
		for (p, q) in move:
			(v1, v2) = (x + p, y + q)
			if ans[v1][v2] == -1:
				not_yet.append((v1, v2))
				ans[v1][v2] = ans[x][y]
		if len(not_yet) == 0:
			while len(one_time) > 0:
				(x2, y2) = one_time.pop()
				for (v1, v2) in move2:
					(i, j) = (x2 + v1, y2 + v2)
					if ans[i][j] == -1:
						ans[i][j] = ans[x2][y2] + 1
						not_yet.append((i, j))
	print(ans[dh][dw])

def __starting_point():
	main()
__starting_point()


from collections import deque
(H, W) = list(map(int, input().split()))
start = list(map(lambda x: int(x) - 1, input().split()))
goal = list(map(lambda x: int(x) - 1, input().split()))
A = [input() for _ in range(H)]
visited = [[0] * W for _ in range(H)]
B = deque([[start[0], start[1], 0]])
warp = []
for i in range(-2, 3):
	for j in range(-2, 3):
		warp.append([i, j])
num = -1
while B:
	(y, x, n) = B.popleft()
	if visited[y][x] == 1:
		continue
	if [y, x] == goal:
		num = n
		break
	visited[y][x] = 1
	for (dy, dx) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		if (y + dy < 0) | (x + dx < 0) | (y + dy >= H) | (x + dx >= W):
			continue
		if (A[y + dy][x + dx] == '.') & (visited[y + dy][x + dx] == 0):
			B.appendleft([y + dy, x + dx, n])
	for (dy, dx) in warp:
		if (y + dy < 0) | (x + dx < 0) | (y + dy >= H) | (x + dx >= W):
			continue
		if (A[y + dy][x + dx] == '.') & (visited[y + dy][x + dx] == 0):
			B.append([y + dy, x + dx, n + 1])
print(num)


def zero_origin(s: str) -> int:
	return int(s) - 1
(h, w) = map(int, input().split())
(ch, cw) = map(zero_origin, input().split())
(dh, dw) = map(zero_origin, input().split())
s = [input() for _ in range(h)]
active = [[True if s[i][j] == '.' else False for j in range(w)] for i in range(h)]
magic = 0
stack = [(ch, cw)]
active[ch][cw] = False
visited = []
while stack:
	(cur_i, cur_j) = stack.pop()
	visited.append((cur_i, cur_j))
	for (di, dj) in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
		i = cur_i + di
		j = cur_j + dj
		if 0 <= i < h and 0 <= j < w and active[i][j]:
			stack.append((i, j))
			active[i][j] = False
	if not active[dh][dw]:
		print(magic)
		break
	if not stack:
		magic += 1
		while visited:
			(cur_i, cur_j) = visited.pop()
			for i in range(cur_i - 2, cur_i + 3):
				for j in range(cur_j - 2, cur_j + 3):
					if 0 <= i < h and 0 <= j < w and active[i][j]:
						stack.append((i, j))
						active[i][j] = False
else:
	print(-1)


import sys
from heapq import *
(H, W) = map(int, input().split())
(si, sj) = [int(x) - 1 for x in input().split()]
(ti, tj) = [int(x) - 1 for x in input().split()]
A = list(sys.stdin)
ans = -1
hp = [(0, si, sj)]
dirs = [-2, -1, 0, 1, 2]
dist = [[float('inf')] * W for _ in range(H)]
dist[si][sj] = 0
while hp:
	(k, i, j) = heappop(hp)
	if i == ti and j == tj:
		ans = k
		break
	if k > dist[i][j]:
		continue
	for di in dirs:
		for dj in dirs:
			if di == dj == 0:
				continue
			(ni, nj) = (i + di, j + dj)
			if not (0 <= ni < H and 0 <= nj < W):
				continue
			if A[ni][nj] == '#':
				continue
			if abs(di) + abs(dj) == 1:
				nk = k
			else:
				nk = k + 1
			if nk >= dist[ni][nj]:
				continue
			dist[ni][nj] = nk
			heappush(hp, (nk, ni, nj))
print(ans)


from heapq import heappush, heappop
from collections import deque
(h, w) = map(int, input().split())
(sx, sy) = map(int, input().split())
sx -= 1
sy -= 1
(gx, gy) = map(int, input().split())
gx -= 1
gy -= 1
g = [list(input()) for _ in range(h)]
v = [[0 for j in range(w)] for i in range(h)]
v2 = [[0 for j in range(w)] for i in range(h)]
q = deque([])
q.append([0, sx, sy])
while q:
	(c, x, y) = q.popleft()
	if x == gx and y == gy:
		print(c)
		exit()
	if v[x][y] == 1:
		continue
	v[x][y] = 1
	for a in range(-2, 3):
		for b in range(-2, 3):
			if a == b == 0:
				continue
			if a * b == 0 and abs(a + b) == 1:
				nx = x + a
				ny = y + b
				if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (v[nx][ny] == 0):
					q.appendleft([c, nx, ny])
				continue
			nx = x + a
			ny = y + b
			if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (v[nx][ny] == 0) and (v2[nx][ny] == 0):
				q.append([c + 1, nx, ny])
				v2[nx][ny] = 1
print(-1)


from collections import deque

def main():
	(h, w) = map(int, input().split())
	(ch, cw) = map(lambda x: int(x) + 1, input().split())
	(dh, dw) = map(lambda x: int(x) + 1, input().split())
	s = [['#'] * (w + 4) for _ in range(2)] + [['#'] * 2 + list(input()) + ['#'] * 2 for _ in range(h)] + [['#'] * (w + 4) for _ in range(2)]
	m1 = ((-1, 0), (0, -1), (0, 1), (1, 0))
	m2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i) + abs(j) > 1]
	a = deque([(ch, cw)])
	b = deque()
	i = 0
	while a:
		while a:
			(ah, aw) = a.popleft()
			if s[ah][aw] != '.':
				continue
			b.append((ah, aw))
			s[ah][aw] = i
			for (bh, bw) in m1:
				(bh, bw) = (ah + bh, aw + bw)
				if s[bh][bw] == '.':
					a.append((bh, bw))
		while b:
			(ah, aw) = b.popleft()
			for (bh, bw) in m2:
				(bh, bw) = (ah + bh, aw + bw)
				if s[bh][bw] == '.':
					a.append((bh, bw))
		i += 1
	ans = s[dh][dw]
	print(ans if ans != '.' else -1)
main()


from collections import deque
(H, W) = map(int, input().split())
(si, sj) = map(int, input().split())
(gi, gj) = map(int, input().split())
(si, sj, gi, gj) = (si - 1, sj - 1, gi - 1, gj - 1)
C = [input() for i in range(H)]
dist = [[10 ** 9] * W for _ in range(H)]
dist[si][sj] = 0
que = deque()
que.append((si, sj))
while que:
	(i, j) = que.popleft()
	d = dist[i][j]
	if i == gi and j == gj:
		break
	for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
		if not (0 <= ni < H and 0 <= nj < W):
			continue
		if d < dist[ni][nj] and C[ni][nj] == '.':
			dist[ni][nj] = d
			que.appendleft((ni, nj))
	for di in range(-2, 3):
		for dj in range(-2, 3):
			(ni, nj) = (i + di, j + dj)
			if not (0 <= ni < H and 0 <= nj < W):
				continue
			if d + 1 < dist[ni][nj] and C[ni][nj] == '.':
				dist[ni][nj] = d + 1
				que.append((ni, nj))
ans = dist[gi][gj]
print(ans if ans != 10 ** 9 else -1)


import sys
input = sys.stdin.readline
from collections import deque
(H, W) = map(int, input().split())
(sh, sw) = map(int, input().split())
(gh, gw) = map(int, input().split())
MAP = [input().strip() for i in range(H)]
ANS = [[1 << 30] * W for i in range(H)]
sh -= 1
sw -= 1
gh -= 1
gw -= 1
ANS[sh][sw] = 0
Q = deque([(sh, sw)])
while Q:
	(x, y) = Q.popleft()
	for (i, j) in [(x - 2, y - 2), (x - 2, y - 1), (x - 2, y), (x - 2, y + 1), (x - 2, y + 2), (x - 1, y - 2), (x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x - 1, y + 2), (x, y - 2), (x, y - 1), (x, y + 1), (x, y + 2), (x + 1, y - 2), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1), (x + 1, y + 2), (x + 2, y - 2), (x + 2, y - 1), (x + 2, y), (x + 2, y + 1), (x + 2, y + 2)]:
		if 0 <= i < H and 0 <= j < W:
			if MAP[i][j] == '.' and abs(i - x) + abs(j - y) == 1 and (ANS[i][j] > ANS[x][y]):
				ANS[i][j] = ANS[x][y]
				Q.appendleft((i, j))
			elif MAP[i][j] == '.' and abs(i - x) + abs(j - y) > 1 and (ANS[i][j] > ANS[x][y] + 1):
				ANS[i][j] = ANS[x][y] + 1
				Q.append((i, j))
if ANS[gh][gw] == 1 << 30:
	print(-1)
else:
	print(ANS[gh][gw])


from collections import deque
(h, w) = map(int, input().split())
(Ch, Cw) = map(lambda x: int(x) - 1, input().split())
(Dh, Dw) = map(lambda x: int(x) - 1, input().split())
(dy, dx) = ((-1, 0, 1, 0), (0, -1, 0, 1))
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
	(c, y, x) = que.popleft()
	if c > maze[y][x]:
		continue
	if y == Dh and x == Dw:
		break
	for i in range(4):
		(y2, x2) = (y + dy[i], x + dx[i])
		if 0 <= y2 < h and 0 <= x2 < w and (c < maze[y2][x2]):
			maze[y2][x2] = c
			que.appendleft((c, y2, x2))
	for i in range(-2, 3):
		for j in range(-2, 3):
			(y3, x3, c2) = (y + i, x + j, c + 1)
			if 0 <= y3 < h and 0 <= x3 < w and (c2 < maze[y3][x3]):
				maze[y3][x3] = c2
				que.append((c2, y3, x3))
ans = maze[Dh][Dw]
if ans == float('inf'):
	print(-1)
else:
	print(ans)


from collections import deque
INF = 10 ** 10
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
m = [list(input()) for _ in range(H)]
s = (Ch - 1, Cw - 1)
g = (Dh - 1, Dw - 1)
d = [[INF] * W for _ in range(H)]
d[s[0]][s[1]] = 0
q = deque()
q.append(s)
while q:
	(y, x) = q.pop()
	for (dy, dx) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
		ny = y + dy
		nx = x + dx
		if ny < 0 or ny >= H or nx < 0 or (nx >= W):
			continue
		if m[ny][nx] == '.' and d[ny][nx] > d[y][x]:
			q.append((ny, nx))
			d[ny][nx] = d[y][x]
	for dy in range(-2, 3):
		for dx in range(-2, 3):
			if abs(dy) + abs(dx) <= 1:
				continue
			ny = y + dy
			nx = x + dx
			if ny < 0 or ny >= H or nx < 0 or (nx >= W):
				continue
			if m[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
				q.appendleft((ny, nx))
				d[ny][nx] = d[y][x] + 1
ans = d[g[0]][g[1]]
if ans < INF:
	print(ans)
else:
	print(-1)


from heapq import *
import sys
input = sys.stdin.readline
inf = int(10000000000.0)
(n, m) = map(int, input().split())
(x, y) = map(int, input().split())
(dx, dy) = map(int, input().split())
(x, y, dx, dy) = (x - 1, y - 1, dx - 1, dy - 1)
matrix = [list(input().strip()) for _ in range(n)]
v = [[inf for _ in range(m)] for _ in range(n)]
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def valid(x, y):
	return 0 <= x < n and 0 <= y < m and (matrix[x][y] != '#')
v[x][y] = 0
q = [(0, (x, y))]
while q:
	(d, node) = heappop(q)
	for i in moves:
		(xx, yy) = (node[0] + i[0], node[1] + i[1])
		if valid(xx, yy) and v[xx][yy] > d:
			v[xx][yy] = d
			heappush(q, (v[xx][yy], (xx, yy)))
	for i in range(node[0] - 2, node[0] + 3):
		for j in range(node[1] - 2, node[1] + 3):
			if valid(i, j) and v[i][j] > d + 1:
				v[i][j] = d + 1
				heappush(q, (v[i][j], (i, j)))
if v[dx][dy] == inf:
	print(-1)
else:
	print(v[dx][dy])


from collections import deque
INF = 1001001001
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
my = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
mx = [2, 1, 0, -1, -2, 2, 1, -1, -2, 2, -2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
(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 = [list(input()) for i in range(h)]
dist = [[INF for i in range(w)] for j in range(h)]
dist[ch][cw] = 0
d = deque([])
d.append([ch, cw])
while d:
	(nowh, noww) = d.popleft()
	for i in range(4):
		th = nowh + dy[i]
		tw = noww + dx[i]
		if 0 <= th <= h - 1 and 0 <= tw <= w - 1 and (dist[th][tw] > dist[nowh][noww]) and (s[th][tw] == '.'):
			d.appendleft([th, tw])
			dist[th][tw] = dist[nowh][noww]
	for i in range(20):
		th = nowh + my[i]
		tw = noww + mx[i]
		if 0 <= th <= h - 1 and 0 <= tw <= w - 1 and (dist[th][tw] > dist[nowh][noww] + 1) and (s[th][tw] == '.'):
			d.append([th, tw])
			dist[th][tw] = dist[nowh][noww] + 1
ans = dist[dh][dw]
if ans == INF:
	ans = -1
print(ans)


from collections import deque

def main():
	(h, w) = map(int, input().split())
	(c1, c2) = map(lambda x: int(x) + 1, input().split())
	(d1, d2) = map(lambda x: int(x) + 1, input().split())
	work1 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	work2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + work1]
	memo = ['#' * (w + 4)] * 2 + ['##' + input() + '##' for _ in range(h)] + ['#' * (w + 4)] * 2
	dist = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if memo[i][j] == '#':
				dist[i][j] = float('inf')
	que1 = deque([(c1, c2)])
	que2 = deque([])
	dist[c1][c2] = 0
	while que1:
		(y, x) = que1.popleft()
		score = dist[y][x]
		que2.append((y, x))
		for (py, px) in work1:
			(ny, nx) = (y + py, x + px)
			if dist[ny][nx] == -1:
				dist[ny][nx] = score
				que1.append((ny, nx))
		if len(que1) == 0:
			while que2:
				(y, x) = que2.popleft()
				for (py, px) in work2:
					(ny, nx) = (y + py, x + px)
					if dist[ny][nx] == -1:
						dist[ny][nx] = score + 1
						que1.append((ny, nx))
	print(dist[d1][d2])

def __starting_point():
	main()
__starting_point()


(H, W) = list(map(int, input().split()))
(Ch, Cw) = list(map(int, input().split()))
(Dh, Dw) = list(map(int, input().split()))
Ch += 1
Cw += 1
Dh += 1
Dw += 1
start = (Ch, Cw)
S = ['#' * (W + 4)]
S.append('#' * (W + 4))
for k in range(H):
	S.append('##' + input() + '##')
S.append('#' * (W + 4))
S.append('#' * (W + 4))
counter = [[-1 for _ in range(W + 4)] for _ in range(H + 4)]
for k in range(2, H + 2):
	for j in range(2, W + 2):
		if S[k][j] == '.':
			counter[k][j] = 10 ** 7
counter[Ch][Cw] = 0
now = [start]
now_2 = [start]
while len(now_2) > 0:
	new = []
	for item in now_2:
		x = item[0]
		y = item[1]
		if counter[x + 1][y] == 10 ** 7:
			counter[x + 1][y] = 0
			new.append((x + 1, y))
		if counter[x][y + 1] == 10 ** 7:
			counter[x][y + 1] = 0
			new.append((x, y + 1))
		if counter[x - 1][y] == 10 ** 7:
			counter[x - 1][y] = 0
			new.append((x - 1, y))
		if counter[x][y - 1] == 10 ** 7:
			counter[x][y - 1] = 0
			new.append((x, y - 1))
	now += new
	now_2 = new
if counter[Dh][Dw] == 0:
	print(0)
	return
ans = 0
while counter[Dh][Dw] == 10 ** 7:
	if len(now) == 0:
		print(-1)
		return
	nextlist = []
	ans += 1
	for item in now:
		x = item[0]
		y = item[1]
		if counter[x + 2][y + 2] > ans:
			counter[x + 2][y + 2] = ans
			nextlist.append((x + 2, y + 2))
		if counter[x + 2][y + 1] > ans:
			counter[x + 2][y + 1] = ans
			nextlist.append((x + 2, y + 1))
		if counter[x + 2][y] > ans:
			counter[x + 2][y] = ans
			nextlist.append((x + 2, y))
		if counter[x + 2][y - 1] > ans:
			counter[x + 2][y - 1] = ans
			nextlist.append((x + 2, y - 1))
		if counter[x + 2][y - 2] > ans:
			counter[x + 2][y - 2] = ans
			nextlist.append((x + 2, y - 2))
		if counter[x + 1][y + 2] > ans:
			counter[x + 1][y + 2] = ans
			nextlist.append((x + 1, y + 2))
		if counter[x + 1][y - 2] > ans:
			counter[x + 1][y - 2] = ans
			nextlist.append((x + 1, y - 2))
		if counter[x][y + 2] > ans:
			counter[x][y + 2] = ans
			nextlist.append((x, y + 2))
		if counter[x][y - 2] > ans:
			counter[x][y - 2] = ans
			nextlist.append((x, y - 2))
		if counter[x - 2][y + 2] > ans:
			counter[x - 2][y + 2] = ans
			nextlist.append((x - 2, y + 2))
		if counter[x - 2][y + 1] > ans:
			counter[x - 2][y + 1] = ans
			nextlist.append((x - 2, y + 1))
		if counter[x - 2][y] > ans:
			counter[x - 2][y] = ans
			nextlist.append((x - 2, y))
		if counter[x - 2][y - 1] > ans:
			counter[x - 2][y - 1] = ans
			nextlist.append((x - 2, y - 1))
		if counter[x - 2][y - 2] > ans:
			counter[x - 2][y - 2] = ans
			nextlist.append((x - 2, y - 2))
		if counter[x - 1][y + 2] > ans:
			counter[x - 1][y + 2] = ans
			nextlist.append((x - 1, y + 2))
		if counter[x - 1][y - 2] > ans:
			counter[x - 1][y - 2] = ans
			nextlist.append((x - 1, y - 2))
		if counter[x - 1][y - 1] > ans:
			counter[x - 1][y - 1] = ans
			nextlist.append((x - 1, y - 1))
		if counter[x - 1][y + 1] > ans:
			counter[x - 1][y + 1] = ans
			nextlist.append((x - 1, y + 1))
		if counter[x + 1][y + 1] > ans:
			counter[x + 1][y + 1] = ans
			nextlist.append((x + 1, y + 1))
		if counter[x + 1][y - 1] > ans:
			counter[x + 1][y - 1] = ans
			nextlist.append((x + 1, y - 1))
	now_2 = nextlist
	while len(now_2) > 0:
		new = []
		for item in now_2:
			x = item[0]
			y = item[1]
			if counter[x + 1][y] == 10 ** 7:
				counter[x + 1][y] = 0
				new.append((x + 1, y))
			if counter[x][y + 1] == 10 ** 7:
				counter[x][y + 1] = 0
				new.append((x, y + 1))
			if counter[x - 1][y] == 10 ** 7:
				counter[x - 1][y] = 0
				new.append((x - 1, y))
			if counter[x][y - 1] == 10 ** 7:
				counter[x][y - 1] = 0
				new.append((x, y - 1))
		nextlist += new
		now_2 = new
	now = nextlist
	if ans > 10 ** 7:
		print(-1)
		return
print(ans)


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()
	P = [[-1 for _ in range(W)] for h in range(H)]
	q.append((0, sh, sw))
	while q:
		(d, h, w) = q.popleft()
		if P[h][w] == -1:
			P[h][w] = d
			for dh in range(-2, 3):
				for dw in range(-2, 3):
					if 0 <= h + dh < H and 0 <= w + dw < W and (S[h + dh][w + dw] == '.') and (P[h + dh][w + dw] == -1):
						if abs(dh) + abs(dw) == 1:
							q.appendleft((d, h + dh, w + dw))
						else:
							q.append((d + 1, h + dh, w + dw))
	print(P[fh][fw])
	return 0
solve()


from collections import deque
(H, W) = map(int, input().split())
(CH, CW) = map(int, input().split())
(DH, DW) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
d = [[-1 for i in range(W)] for j in range(H)]
Q = deque([[CH - 1, CW - 1, 0]])
while Q:
	(x, y, cnt) = Q.popleft()
	if d[x][y] != -1:
		continue
	d[x][y] = cnt
	for tx in range(-2, 3):
		for ty in range(-2, 3):
			nx = x + tx
			ny = y + ty
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == '.'):
				if abs(tx) + abs(ty) == 1:
					Q.appendleft([nx, ny, cnt])
				elif abs(tx) + abs(ty) >= 2:
					Q.append([nx, ny, cnt + 1])
ans = d[DH - 1][DW - 1]
print(ans)


INF = 10 ** 9
from heapq import heappop, heappush
(H, W) = (int(i) for i in input().split())
(Ch, Cw) = (int(i) - 1 for i in input().split())
(Dh, Dw) = (int(i) - 1 for i in input().split())
S = [input() for i in range(H)]
dist = [[INF] * W for _ in range(H)]
dist[Ch][Cw] = 0
que = [(0, Ch * W + Cw)]
while que:
	(u_dist, u) = heappop(que)
	(uh, uw) = (u // W, u % W)
	if dist[uh][uw] < u_dist:
		continue
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			nh = uh + dh
			nw = uw + dw
			if nh < 0 or H <= nh or nw < 0 or (W <= nw):
				continue
			if S[nh][nw] == '#':
				continue
			cost = 0 if abs(dh) + abs(dw) <= 1 else 1
			if dist[nh][nw] > dist[uh][uw] + cost:
				dist[nh][nw] = dist[uh][uw] + cost
				heappush(que, (dist[nh][nw], nh * W + nw))
if dist[Dh][Dw] == INF:
	print(-1)
else:
	print(dist[Dh][Dw])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :], i8, i8, i8, i8))
def main(ss, ch, cw, dh, dw):
	inf = 1 << 30
	(h, w) = ss.shape
	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 abs(xx) + abs(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
				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))


import heapq

def solve():
	(H, W) = map(int, input().split())
	(sy, sx) = map(lambda x: int(x) - 1, input().split())
	(ty, tx) = map(lambda x: int(x) - 1, input().split())
	graph = [input() for i in range(H)]
	INF = 10 ** 9
	dist = [INF] * (H * W)
	que = []

	def push(y, x, d):
		v = y * W + x
		if dist[v] <= d:
			return
		dist[v] = d
		heapq.heappush(que, (d, v))
	push(sy, sx, 0)
	while que:
		(d, v) = heapq.heappop(que)
		(y, x) = divmod(v, W)
		if dist[v] < d:
			continue
		for dy in range(-2, 3):
			for dx in range(-2, 3):
				(ny, nx) = (y + dy, x + dx)
				if ny < 0 or ny >= H or nx < 0 or (nx >= W):
					continue
				if graph[ny][nx] == '#':
					continue
				push(ny, nx, d + (abs(dy) + abs(dx) > 1))
	t = ty * W + tx
	if dist[t] == INF:
		return -1
	else:
		return dist[t]
print(solve())


from collections import deque
import sys
input = sys.stdin.readline
inf = float('inf')

def BFS():
	D = [[inf for _ in range(w)] for _ in range(h)]
	queue = deque()
	queue.append([Cx - 1, Cy - 1, 0])
	D[Cx - 1][Cy - 1] = 0
	while len(queue) > 0:
		(x, y, cnt) = queue.popleft()
		for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
			(X, Y) = (x + i, y + j)
			if 0 <= X < h and 0 <= Y < w:
				if S[X][Y] == '.' and D[X][Y] > cnt:
					D[X][Y] = cnt
					queue.appendleft([X, Y, cnt])
		for X in range(max(0, x - 2), min(h, x + 3)):
			for Y in range(max(0, y - 2), min(w, y + 3)):
				if S[X][Y] == '.' and D[X][Y] > cnt + 1:
					D[X][Y] = cnt + 1
					queue.append([X, Y, cnt + 1])
	return D[Dx - 1][Dy - 1]
(h, w) = map(int, input().split())
(Cx, Cy) = map(int, input().split())
(Dx, Dy) = map(int, input().split())
S = [list(input()) for _ in range(h)]
D = BFS()
print(D if D != inf else -1)


def l():
	return [int(x) for x in input().split()]

def main():
	(H, W) = l()
	(ch, cw) = l()
	(dh, dw) = l()
	ch -= 1
	cw -= 1
	dw -= 1
	dh -= 1
	s = [[-2 if x == '#' else -1 for x in list(input())] for _ in range(H)]
	pad1 = [-2, -2]
	pad2 = [[-2] * (W + 4)] * 2
	s = pad2 + [pad1 + x + pad1 for x in s] + pad2
	move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	move2 = list(set([(i, j) for i in range(-2, 3) for j in range(-2, 3)]) - set(move1) - set([(0, 0)]))
	q1 = [(0, ch + 2, cw + 2)]
	q2 = []
	s[ch + 2][cw + 2] = 0

	def mark(c, h, w):
		if -2 <= h < H + 2 and -2 <= w < W + 2 and (s[h][w] == -1):
			s[h][w] = c
			q1.append((c, h, w))
	while q1:
		(c, h, w) = q1.pop()
		for (i, j) in move1:
			mark(c, h + i, w + j)
		q2.append((c + 1, h, w))
		if not q1:
			for (c, h, w) in q2:
				for (i, j) in move2:
					mark(c, h + i, w + j)
			q2 = []
	ans = s[dh + 2][dw + 2]
	if ans >= 0:
		print(ans)
	else:
		print(-1)
main()


from collections import deque

def main():

	def bfs(h1, w1, dp):
		queue = deque()
		queue_warp = deque()
		queue.append([h1, w1])
		now = 0
		while queue:
			(h1, w1) = queue.popleft()
			fl_up = False
			fl_left = False
			fl_down = False
			fl_right = False
			if h1 > 0:
				if dp[h1 - 1][w1] == -1 or dp[h1 - 1][w1] == -2:
					if m[h1 - 1][w1] == '.':
						dp[h1 - 1][w1] = now
						queue.append([h1 - 1, w1])
					else:
						dp[h1 - 1][w1] = -3
				if dp[h1 - 1][w1] == -3:
					fl_up = True
					if h1 > 1:
						if dp[h1 - 2][w1] == -1:
							if m[h1 - 2][w1] == '.':
								dp[h1 - 2][w1] = -2
								queue_warp.append([h1 - 2, w1])
							else:
								dp[h1 - 2][w1] = -3
			if w1 > 0:
				if dp[h1][w1 - 1] == -1 or dp[h1][w1 - 1] == -2:
					if m[h1][w1 - 1] == '.':
						dp[h1][w1 - 1] = now
						queue.append([h1, w1 - 1])
					else:
						dp[h1][w1 - 1] = -3
				if dp[h1][w1 - 1] == -3:
					fl_left = True
					if w1 > 1:
						if dp[h1][w1 - 2] == -1:
							if m[h1][w1 - 2] == '.':
								dp[h1][w1 - 2] = -2
								queue_warp.append([h1, w1 - 2])
							else:
								dp[h1][w1 - 2] = -3
			if h1 < h - 1:
				if dp[h1 + 1][w1] == -1 or dp[h1 + 1][w1] == -2:
					if m[h1 + 1][w1] == '.':
						dp[h1 + 1][w1] = now
						queue.append([h1 + 1, w1])
					else:
						dp[h1 + 1][w1] = -3
				if dp[h1 + 1][w1] == -3:
					fl_down = True
					if h1 < h - 2:
						if dp[h1 + 2][w1] == -1:
							if m[h1 + 2][w1] == '.':
								dp[h1 + 2][w1] = -2
								queue_warp.append([h1 + 2, w1])
							else:
								dp[h1 + 2][w1] = -3
			if w1 < w - 1:
				if dp[h1][w1 + 1] == -1 or dp[h1][w1 + 1] == -2:
					if m[h1][w1 + 1] == '.':
						dp[h1][w1 + 1] = now
						queue.append([h1, w1 + 1])
					else:
						dp[h1][w1 + 1] = -3
				if dp[h1][w1 + 1] == -3:
					fl_right = True
					if w1 < w - 2:
						if dp[h1][w1 + 2] == -1:
							if m[h1][w1 + 2] == '.':
								dp[h1][w1 + 2] = -2
								queue_warp.append([h1, w1 + 2])
							else:
								dp[h1][w1 + 2] = -3
			if fl_up and fl_left:
				for i in range(max(0, h1 - 2), h1):
					for j in range(max(0, w1 - 2), w1):
						if dp[i][j] == -1:
							if m[i][j] == '.':
								dp[i][j] = -2
								queue_warp.append([i, j])
							else:
								dp[i][j] = -3
			if fl_left and fl_down:
				for i in range(h1 + 1, min(h, h1 + 3)):
					for j in range(max(0, w1 - 2), w1):
						if dp[i][j] == -1:
							if m[i][j] == '.':
								dp[i][j] = -2
								queue_warp.append([i, j])
							else:
								dp[i][j] = -3
			if fl_down and fl_right:
				for i in range(h1 + 1, min(h, h1 + 3)):
					for j in range(w1 + 1, min(w, w1 + 3)):
						if dp[i][j] == -1:
							if m[i][j] == '.':
								dp[i][j] = -2
								queue_warp.append([i, j])
							else:
								dp[i][j] = -3
			if fl_right and fl_up:
				for i in range(max(0, h1 - 2), h1):
					for j in range(w1 + 1, min(w, w1 + 3)):
						if dp[i][j] == -1:
							if m[i][j] == '.':
								dp[i][j] = -2
								queue_warp.append([i, j])
							else:
								dp[i][j] = -3
			if not queue:
				now += 1
				while queue_warp:
					(h1, w1) = queue_warp.popleft()
					if dp[h1][w1] == -2:
						dp[h1][w1] = now
						queue.append([h1, w1])
			if dp[dh - 1][dw - 1] >= 0:
				return dp[dh - 1][dw - 1]
		return dp[dh - 1][dw - 1]
	(h, w) = list(map(int, input().split()))
	(ch, cw) = list(map(int, input().split()))
	(dh, dw) = list(map(int, input().split()))
	m = [[] for i in range(h)]
	dp = [[-1] * w for i in range(h)]
	dp[ch - 1][cw - 1] = 0
	for i in range(h):
		m[i] = input()
	ans = bfs(ch - 1, cw - 1, dp)
	print(ans)
main()


from collections import deque
(H, W) = map(int, input().split())
(C_h, C_w) = map(int, input().split())
(D_h, D_w) = map(int, input().split())
X = [input() for _ in range(H)]
inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))
while q:
	(u, v) = q.popleft()
	for (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		if 0 <= u + i < H and 0 <= v + j < W and (X[u + i][v + j] == '.') and (dist[u + i][v + j] > dist[u][v]):
			dist[u + i][v + j] = dist[u][v]
			q.appendleft((u + i, v + j))
	for i in range(-2, 3):
		for j in range(-2, 3):
			if 0 <= u + i < H and 0 <= v + j < W and (X[u + i][v + j] == '.') and (dist[u + i][v + j] > dist[u][v] + 1):
				dist[u + i][v + j] = dist[u][v] + 1
				q.append((u + i, v + j))
if dist[D_h - 1][D_w - 1] < inf:
	print(dist[D_h - 1][D_w - 1])
else:
	print(-1)


from itertools import product
from collections import deque
(H, W) = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]
C[0] -= 1
C[1] -= 1
D[0] -= 1
D[1] -= 1
a = [-2, -1, 0, 1, 2]
wk = {(1, 0), (-1, 0), (0, 1), (0, -1)}
wp = set(product(a, a)).difference(wk)
wp -= {(0, 0)}
stk = deque([[C[0], C[1], 0]])
dp = [[float('inf')] * W for _ in range(H)]

def BFS():
	while len(stk) > 0:
		l = stk.pop()
		i = l[0]
		j = l[1]
		ct = l[2]
		if ct >= dp[i][j]:
			continue
		dp[i][j] = ct
		for k in wk:
			x = i + k[0]
			y = j + k[1]
			if 0 <= x < H and 0 <= y < W and (S[x][y] == '.'):
				stk.append([x, y, ct])
		for k in wp:
			x = i + k[0]
			y = j + k[1]
			if 0 <= x < H and 0 <= y < W and (S[x][y] == '.'):
				stk.appendleft([x, y, ct + 1])
BFS()
ans = dp[D[0]][D[1]]
if ans == float('inf'):
	print(-1)
else:
	print(dp[D[0]][D[1]])


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
(ch, cw, dh, dw) = (ch - 1, cw - 1, dh - 1, dw - 1)
s = [list(input()) for i in range(h)]
d = [[-1] * w for i in range(h)]
Q = deque([(ch, cw, 0)])
while Q:
	(x, y, broken) = Q.popleft()
	if d[x][y] != -1:
		continue
	d[x][y] = broken
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			if 0 <= x + dx < h and 0 <= y + dy < w and (s[x + dx][y + dy] == '.') and (d[x + dx][y + dy] == -1):
				if abs(dx) + abs(dy) == 1:
					Q.appendleft((x + dx, y + dy, broken))
				else:
					Q.append((x + dx, y + dy, broken + 1))
print(d[dh][dw])


from collections import deque

def main():
	from sys import stdin
	readline = stdin.readline
	from builtins import max, min, range
	INF = 10 ** 6
	(H, W) = list(map(int, readline().split()))
	(Ch, Cw) = [int(x) - 1 for x in readline().split()]
	(Dh, Dw) = [int(x) - 1 for x in readline().split()]
	S = [readline()[:-1] for _ in range(H)]
	t = [[INF] * W for _ in range(H)]
	for h in range(H):
		th = t[h]
		Sh = S[h]
		for w in range(W):
			if Sh[w] == '#':
				th[w] = -1
	t[Ch][Cw] = 0
	q = deque([(Ch, Cw)])
	a = 0
	warpq = []
	while q:
		while q:
			(h, w) = q.popleft()
			warpq.append((h, w))
			if h - 1 >= 0 and t[h - 1][w] > a:
				q.append((h - 1, w))
				t[h - 1][w] = a
			if h + 1 < H and t[h + 1][w] > a:
				q.append((h + 1, w))
				t[h + 1][w] = a
			if w - 1 >= 0 and t[h][w - 1] > a:
				q.append((h, w - 1))
				t[h][w - 1] = a
			if w + 1 < W and t[h][w + 1] > a:
				q.append((h, w + 1))
				t[h][w + 1] = a
		if t[Dh][Dw] != INF:
			break
		a += 1
		for (h, w) in warpq:
			for i in range(max(0, h - 2), min(H, h + 3)):
				ti = t[i]
				for j in range(max(0, w - 2), min(W, w + 3)):
					if ti[j] > a:
						ti[j] = a
						q.append((i, j))
		warpq.clear()
	if t[Dh][Dw] == INF:
		print(-1)
	else:
		print(t[Dh][Dw])
main()


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
from collections import deque
(h, w) = nii()
(ch, cw) = nii()
(dh, dw) = nii()
s = [list(input()) for i in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ans = [[-1 for i in range(w)] for i in range(h)]
ans[ch][cw] = 0
que = deque()
que.append((ch, cw))

def BFS():
	while que:
		(y, x) = que.popleft()
		if y == dh and x == dw:
			print(ans[y][x])
			exit()
		for (dy, dx) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
			ny = y + dy
			nx = x + dx
			if 0 <= ny < h and 0 <= nx < w and (s[ny][nx] != '#'):
				que.appendleft((ny, nx))
				s[ny][nx] = '#'
				ans[ny][nx] = ans[y][x]
			for i in range(-2, 3):
				for j in range(-2, 3):
					ny = y + i
					nx = x + j
					if 0 <= ny < h and 0 <= nx < w and (s[ny][nx] != '#') and (ans[ny][nx] == -1):
						que.append((ny, nx))
						ans[ny][nx] = ans[y][x] + 1
BFS()
print(-1)


from collections import deque
import sys

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

def main():
	(H, W) = map(int, input().split())
	(sh, sw) = map(int, input().split())
	sh -= 1
	sw -= 1
	start = (sh + 2) * (W + 4) + 2 + sw
	(dh, dw) = map(int, input().split())
	dh -= 1
	dw -= 1
	goal = (dh + 2) * (W + 4) + 2 + dw
	field = '#' * (W + 4) * 2
	field += '##' + '####'.join([input() for _ in range(H)]) + '##'
	field += '#' * (W + 4) * 2
	move = [-1, 1, -(W + 4), W + 4]
	ex_left = [-2 * (W + 4) - 2, -(W + 4) - 2, -2, W + 4 - 2, 2 * (W + 4) - 2, -(W + 4) - 1, W + 4 - 1]
	ex_right = [-2 * (W + 4) + 2, -(W + 4) + 2, +2, W + 4 + 2, 2 * (W + 4) + 2, -(W + 4) + 1, W + 4 + 1]
	ex_up = [-2 * (W + 4) - 2, -2 * (W + 4) - 1, -2 * (W + 4), -2 * (W + 4) + 1, -2 * (W + 4) + 2, -(W + 4) - 1, -(W + 4) + 1]
	ex_down = [2 * (W + 4) - 2, 2 * (W + 4) - 1, 2 * (W + 4), 2 * (W + 4) + 1, 2 * (W + 4) + 2, W + 4 - 1, W + 4 + 1]
	INF = 10 ** 18
	num = [INF] * (H + 4) * (W + 4)
	warped = [False] * (H + 4) * (W + 4)

	def bfs(s):
		q = deque()
		num[s] = 0
		q.append((s, 0))
		while q:
			(now, cost) = q.popleft()
			if cost > num[now]:
				continue
			else:
				num[now] = cost
			if now == goal:
				return
			for (i, dx) in enumerate(move):
				nx = now + dx
				if field[nx] == '.' and num[nx] == INF:
					q.appendleft((nx, cost))
					num[nx] = cost
				elif field[nx] == '#':
					if i == 0:
						ex = ex_left
					elif i == 1:
						ex = ex_right
					elif i == 2:
						ex = ex_up
					else:
						ex = ex_down
					for dx2 in ex:
						nx2 = now + dx2
						if field[nx2] == '.' and num[nx2] == INF and (not warped[nx2]):
							q.append((nx2, cost + 1))
							warped[nx2] = True
	bfs(start)
	if num[goal] == INF:
		print(-1)
	else:
		print(num[goal])

def __starting_point():
	main()
__starting_point()


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
path = [[10 ** 10] * w for i in range(h)]
maze = []
for _ in range(h):
	s = input()
	maze.append(s)
walk = [(0, 1), (1, 0), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
Q = deque()
path[ch - 1][cw - 1] = 0
Q.append((ch - 1, cw - 1, 0))
while Q:
	(hi, wi, c) = Q.popleft()
	for (i, j) in walk:
		nh = i + hi
		nw = j + wi
		if 0 <= nh < h and 0 <= nw < w and (maze[nh][nw] == '.') and (path[nh][nw] > c):
			path[nh][nw] = c
			Q.appendleft((nh, nw, c))
	for (i, j) in warp:
		nh = i + hi
		nw = j + wi
		if 0 <= nh < h and 0 <= nw < w and (maze[nh][nw] == '.') and (path[nh][nw] > c + 1):
			path[nh][nw] = c + 1
			Q.append((nh, nw, c + 1))
print(path[dh - 1][dw - 1] if path[dh - 1][dw - 1] < 10 ** 10 else -1)


from collections import deque
from itertools import product
(H, W) = map(int, input().split())
(Ch, Cw) = map(lambda x: int(x) - 1, input().split())
(Dh, Dw) = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(H)]
walkFrom = deque([(Ch, Cw)])
warpFrom = deque()
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
	for (h, w) in moveRange:
		(h_to, w_to) = (h_from + h, w_from + w)
		if 0 <= h_to < H and 0 <= w_to < W and (maze[h_to][w_to] == '.'):
			maze[h_to][w_to] = warpCount
			walkFrom.append((h_to, w_to))
while walkFrom:
	while walkFrom:
		(h, w) = walkFrom.popleft()
		warpFrom.append((h, w))
		move(h, w, WalkRange)
	warpCount += 1
	while warpFrom:
		(h, w) = warpFrom.popleft()
		move(h, w, WarpRange)
goal = maze[Dh][Dw]
print(goal) if not goal in ['.', '#'] else print('-1')


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
(h, w) = na()
(ch, cw) = na()
(dh, dw) = na()
(ch, cw) = (ch - 1, cw - 1)
(dh, dw) = (dh - 1, dw - 1)
s = []
for i in range(h):
	s.append(ns())
from collections import deque
g = [[10000000000] * w for i in range(h)]
g[ch][cw] = 0
d = deque([(ch, cw, 0)])
while d:
	(x, y, num) = d.popleft()
	pq = [(-1, 0), (0, 1), (1, 0), (0, -1)]
	for (p, q) in pq:
		if not (0 <= x + p < h and 0 <= y + q < w):
			continue
		u = s[x + p][y + q]
		if u == '.':
			if num < g[x + p][y + q]:
				g[x + p][y + q] = num
				d.appendleft((x + p, y + q, num))
	for i in range(-2, 3):
		for j in range(-2, 3):
			if not (0 <= x + i < h and 0 <= y + j < w):
				continue
			p = s[x + i][y + j]
			if p == '.':
				if num + 1 < g[x + i][y + j]:
					g[x + i][y + j] = num + 1
					d.append((x + i, y + j, num + 1))
ans = g[dh][dw]
print('-1' if ans == 10000000000 else ans)


from collections import deque

def main():
	(h, w) = list(map(int, input().split()))
	(cy, cx) = list(map(int, input().split()))
	(dy, dx) = list(map(int, input().split()))
	M = ['##' + input() + '##' for x in range(h)]
	for i in range(2):
		M.insert(0, '#' * (w + 4))
		M.append('#' * (w + 4))
	C = [[-1 if M[j][i] == '.' else -2 for i in range(w + 4)] for j in range(h + 4)]
	C[-~cy][-~cx] = 0
	(QA, QB) = (deque(), deque())
	QA.append((-~cy, -~cx, 0))
	W = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if abs(i) + abs(j) > 1]
	while QA:
		(h, w, c) = QA.popleft()
		QB.append((h, w, c))
		for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
			(dh, dw) = (h + i, w + j)
			if C[dh][dw] == -1:
				C[dh][dw] = c
				QA.appendleft((dh, dw, c))
		if QA:
			continue
		while QB:
			(h, w, c) = QB.popleft()
			for (i, j) in W:
				(dh, dw) = (h + i, w + j)
				if C[dh][dw] == -1:
					C[dh][dw] = -~c
					QA.append((dh, dw, -~c))
		if C[-~dy][-~dx] != -1:
			print(C[-~dy][-~dx])
			return
	print(C[-~dy][-~dx])

def __starting_point():
	main()
__starting_point()


(H, W) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
(sy, sx) = (sy - 1, sx - 1)
(gy, gx) = (gy - 1, gx - 1)
S = [input() for i in range(H)]
import heapq
INF = float('inf')
dist = [[INF] * W for i in range(H)]
dist[sy][sx] = 0
hq = [(0, sx + sy * W)]
heapq.heapify(hq)
while hq:
	(d, v) = heapq.heappop(hq)
	(y, x) = divmod(v, W)
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			if dx == dy == 0:
				continue
			(nx, ny) = (x + dx, y + dy)
			if not 0 <= nx < W:
				continue
			if not 0 <= ny < H:
				continue
			if S[ny][nx] == '#':
				continue
			if abs(dx) + abs(dy) <= 1:
				if dist[ny][nx] <= dist[y][x]:
					continue
				dist[ny][nx] = dist[y][x]
				heapq.heappush(hq, (d, nx + ny * W))
			else:
				if dist[ny][nx] <= dist[y][x] + 1:
					continue
				dist[ny][nx] = dist[y][x] + 1
				heapq.heappush(hq, (d + 1, nx + ny * W))
print(-1 if dist[gy][gx] == INF else dist[gy][gx])


from collections import deque
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
l = [[1 if i == '#' else 0 for i in input()] for _ in range(H)]
q = deque([(0, (Ch - 1, Cw - 1))])
INF = 10 ** 12
costs = [[INF] * W for _ in range(H)]
costs[Ch - 1][Cw - 1] = 0
while q:
	(cost, pos) = q.popleft()
	(h, w) = pos
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			if dh == 0 and dw == 0:
				continue
			(hh, ww) = (h + dh, w + dw)
			if not (0 <= hh < H and 0 <= ww < W):
				continue
			if l[hh][ww]:
				continue
			if (abs(dh) == 1 and dw == 0 or (dh == 0 and abs(dw) == 1)) and costs[hh][ww] > costs[h][w]:
				costs[hh][ww] = costs[h][w]
				q.appendleft((cost, (hh, ww)))
			elif costs[hh][ww] > costs[h][w] + 1:
				costs[hh][ww] = costs[h][w] + 1
				q.append((cost + 1, (hh, ww)))
ans = costs[Dh - 1][Dw - 1]
print(ans if ans != INF else -1)


from sys import stdin
import collections
input = stdin.readline
(Y, X) = map(int, input().split())
(sy, sx) = map(int, input().split())
sy -= 1
sx -= 1
(ey, ex) = map(int, input().split())
ey -= 1
ex -= 1
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
dis = [[float('inf')] * X for _ in range(Y)]
Q = collections.deque()
Q.append((sy, sx))
dis[sy][sx] = 0
while Q:
	(cy, cx) = Q.popleft()
	for (ny, nx) in [(cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)]:
		if 0 <= ny < Y and 0 <= nx < X and (grid[ny][nx] == '.') and (dis[ny][nx] > dis[cy][cx]):
			Q.appendleft((ny, nx))
			dis[ny][nx] = dis[cy][cx]
	for dy in range(-2, 3):
		for dx in range(-2, 3):
			ny = cy + dy
			nx = cx + dx
			if 0 <= ny < Y and 0 <= nx < X and (grid[ny][nx] == '.') and (dis[ny][nx] > dis[cy][cx] + 1):
				Q.append((ny, nx))
				dis[ny][nx] = dis[cy][cx] + 1
print(dis[ey][ex] if dis[ey][ex] != float('inf') else -1)


from collections import *
(H, W) = map(int, input().split())
(CH, CW) = map(int, input().split())
(CH, CW) = (CH - 1, CW - 1)
(DH, DW) = map(int, input().split())
(DH, DW) = (DH - 1, DW - 1)
S = [input() for i in range(H)]
Q = deque()
INF = 10 ** 9
D = [[INF] * W for i in range(H)]
D[CH][CW] = 0
Q.append((CH, CW))
w4x = [[0, 1, 0, -1], []]
w4y = [[1, 0, -1, 0], []]
for i in range(5):
	for j in range(5):
		if abs(i - 2) + abs(j - 2) <= 1:
			continue
		w4x[1].append(i - 2)
		w4y[1].append(j - 2)
v = 0
w = 0
d = 0
while len(Q):
	v = Q.popleft()
	for j in range(2):
		for i in range(len(w4x[j])):
			w = (v[0] + w4y[j][i], v[1] + w4x[j][i])
			if min(w) < 0 or w[0] >= H or w[1] >= W:
				continue
			if S[w[0]][w[1]] == '#':
				continue
			d = D[v[0]][v[1]] + j
			if D[w[0]][w[1]] > d:
				D[w[0]][w[1]] = d
				if j:
					Q.append(w)
				else:
					Q.appendleft(w)
if D[DH][DW] == INF:
	print(-1)
else:
	print(D[DH][DW])


from collections import deque
import copy
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
S = [list(str(input())) for i in range(H)]
field2 = copy.deepcopy(S)
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
temp = deque()

def dfs2(x, y):
	field2[x][y] = '#'
	temp.append([x, y])
	for i in range(4):
		nx = x + move[i][0]
		ny = y + move[i][1]
		if 0 <= nx and nx < H and (0 <= ny) and (ny < W) and (field2[nx][ny] == '.'):
			dfs2(nx, ny)
	return temp
start = dfs2(Ch - 1, Cw - 1)
while True:
	if field2[Dh - 1][Dw - 1] == '#':
		print(ans)
		exit()
	else:
		for i in range(len(start)):
			ttemp = start.popleft()
			for hh in range(-2, 3):
				for ww in range(-2, 3):
					nnx = ttemp[0] + hh
					nny = ttemp[1] + ww
					if 0 <= nnx and nnx < H and (0 <= nny) and (nny < W) and (field2[nnx][nny] == '.'):
						dfs2(nnx, nny)
		ans += 1
	if len(start) == 0:
		print(-1)
		exit()


from collections import deque
(H, W) = map(int, input().split())
(Si, Sj) = map(int, input().split())
(Gi, Gj) = map(int, input().split())
S = ['#' * (W + 2)] + ['#' + input() + '#' for _ in range(H)] + ['#' * (W + 2)]
INF = float('inf')
D = [[INF] * (W + 2) for _ in range(H + 2)]
D[Si][Sj] = 0
Q = deque([(0, Si, Sj)])
while Q:
	(c, i, j) = Q.popleft()
	if (i, j) == (Gi, Gj):
		print(D[i][j])
		quit()
	for (ni, nj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
		if 1 <= ni <= H and 1 <= nj <= W and (D[ni][nj] > c) and (S[ni][nj] == '.'):
			D[ni][nj] = c
			Q.appendleft((c, ni, nj))
	for di in range(-2, 3):
		for dj in range(-2, 3):
			(ni, nj) = (i + di, j + dj)
			if 1 <= ni <= H and 1 <= nj <= W and ((di, dj) not in [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]) and (D[ni][nj] > c + 1) and (S[ni][nj] == '.'):
				D[ni][nj] = c + 1
				Q.append((c + 1, ni, nj))
print(-1)


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(lambda x: int(x) - 1, input().split())
(dh, dw) = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(H)]
INF = 10 ** 9
m = [[INF] * W for _ in range(H)]
m[ch][cw] = 0
q = deque()
q.append((ch, cw, 0))
cnt = 0
while q:
	cnt += 1
	(h, w, n) = q.popleft()
	for (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		if (h + i < 0 or w + j < 0) or (h + i >= H or w + j >= W):
			continue
		if m[h + i][w + j] <= n:
			continue
		if s[h + i][w + j] == '#':
			continue
		m[h + i][w + j] = n
		q.appendleft((h + i, w + j, n))
	for i in range(-2, 3):
		for j in range(-2, 3):
			if (h + i < 0 or w + j < 0) or (h + i >= H or w + j >= W):
				continue
			if m[h + i][w + j] <= n + 1:
				continue
			if s[h + i][w + j] == '#':
				continue
			m[h + i][w + j] = n + 1
			q.append((h + i, w + j, n + 1))
if m[dh][dw] == INF:
	print(-1)
else:
	print(m[dh][dw])


import heapq
(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 _ in range(H):
	s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]
q = []
heapq.heappush(q, (0, (ch, cw)))
while q:
	(c, (h, w)) = heapq.heappop(q)
	if cs[h][w] < c:
		continue
	cs[h][w] = c
	for (nh, nw) in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
		if 0 <= nh < H and 0 <= nw < W and (s[nh][nw] == '.') and (c < cs[nh][nw]):
			cs[nh][nw] = c
			heapq.heappush(q, (c, (nh, nw)))
	for nh in range(h - 2, h + 3):
		for nw in range(w - 2, w + 3):
			if 0 <= nh < H and 0 <= nw < W and (s[nh][nw] == '.') and (c + 1 < cs[nh][nw]):
				cs[nh][nw] = c + 1
				heapq.heappush(q, (c + 1, (nh, nw)))
print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])


from collections import deque
(H, W) = map(int, input().split())
(sy, sx) = [int(i) - 1 for i in input().split()]
(gy, gx) = [int(i) - 1 for i in input().split()]
c = []
for i in [0] * H:
	c.append(input())
dic = []
for i in range(-2, 3):
	for j in range(-2, 3):
		if i != 0 or j != 0:
			dic.append((i, j))
INF = 10 ** 9
vis = [[INF] * W for _ in [0] * H]
q = deque()
q.appendleft((sx, sy))
vis[sy][sx] = 0
res = -1
while q:
	(x, y) = q.popleft()
	if (x, y) == (gx, gy):
		res = vis[y][x]
	for (dx, dy) in dic:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx <= W - 1 and 0 <= ny <= H - 1:
			if vis[ny][nx] > vis[y][x] and c[ny][nx] != '#':
				if dx ** 2 + dy ** 2 < 2:
					vis[ny][nx] = vis[y][x]
					q.appendleft((nx, ny))
				else:
					vis[ny][nx] = vis[y][x] + 1
					q.append((nx, ny))
		if res > -1:
			break
	if res > -1:
		break
print(res)


from collections import deque
INF = -1
(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 = []
for i in range(H):
	S.append(list(input()))
ans = [[INF] * W for _ in range(H)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
que = deque([(Ch, Cw, 0)])
while len(que) != 0:
	p = que.popleft()
	if ans[p[0]][p[1]] == INF:
		ans[p[0]][p[1]] = p[2]
		if p[0] == Dh and p[1] == Dw:
			break
		for i in range(4):
			h = p[0] + dx[i]
			w = p[1] + dy[i]
			if (0 <= h and H > h) and (0 <= w and W > w) and (S[h][w] != '#') and (ans[h][w] == INF):
				que.appendleft((h, w, p[2]))
		for i in range(-2, 3):
			for j in range(-2, 3):
				h = p[0] + i
				w = p[1] + j
				if (0 <= h and H > h) and (0 <= w and W > w) and (S[h][w] != '#') and (ans[h][w] == INF):
					que.append((h, w, p[2] + 1))
print(ans[Dh][Dw])


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 = [0 for _ in range(H + 4)]
	M[0] = ['#'] * (W + 4)
	M[1] = ['#'] * (W + 4)
	M[-2] = ['#'] * (W + 4)
	M[-1] = ['#'] * (W + 4)
	for h in range(2, H + 2):
		M[h] = ['#'] * 2 + list(input().strip()) + ['#'] * 2
	ans = 0
	q = set([(Ch, Cw)])
	M[Ch][Cw] = '#'
	dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	while True:
		newq = set()
		while q:
			q_ = set()
			for (h, w) in q:
				if h == Dh and w == Dw:
					print(ans)
					return True
				newq.add((h, w))
				for (dh, dw) in dhdw:
					if M[h + dh][w + dw] == '#':
						continue
					q_.add((h + dh, w + dw))
					M[h + dh][w + dw] = '#'
			q = q_
		if newq:
			for (h, w) in newq:
				for dh in range(-2, 3):
					for dw in range(-2, 3):
						if M[h + dh][w + dw] == '.':
							q.add((h + dh, w + dw))
							M[h + dh][w + dw] = '#'
		if len(q):
			ans += 1
		else:
			print(-1)
			return True

def __starting_point():
	main()
__starting_point()


(h, w) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
(Ch, Cw) = (Ch - 1, Cw - 1)
(Dh, Dw) = (Dh - 1, Dw - 1)
todo = [[0, Ch, Cw]]
ntodo = []
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
toho = [[0, 1], [0, -1], [1, 0], [-1, 0]]
wiz = [[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]]
while todo or ntodo:
	if not todo:
		todo = ntodo
		ntodo = []
	(cnt, nh, nw) = todo.pop()
	if d[nh][nw] < cnt:
		continue
	for (dh, dw) in toho:
		if 0 <= nh + dh < h and 0 <= nw + dw < w and (s[nh + dh][nw + dw] != '#'):
			if d[nh + dh][nw + dw] == -1 or d[nh + dh][nw + dw] > cnt:
				d[nh + dh][nw + dw] = cnt
				todo.append([cnt, nh + dh, nw + dw])
	for (dh, dw) in wiz:
		if 0 <= nh + dh < h and 0 <= nw + dw < w and (s[nh + dh][nw + dw] != '#'):
			if d[nh + dh][nw + dw] == -1 or d[nh + dh][nw + dw] > cnt + 1:
				d[nh + dh][nw + dw] = cnt + 1
				ntodo.append([cnt + 1, nh + dh, nw + dw])
print(d[Dh][Dw])


from collections import deque

def solve(h, w, ch, cw, dh, dw, s):
	(W, H) = (w + 5, h + 5)

	def pos(r, c):
		return (r + 2) * W + c + 2
	G = [0] * (W * H)
	label = 0
	for r in range(h):
		for c in range(w):
			if s[r][c] == '.' and G[pos(r, c)] == 0:
				label += 1
				que = deque([(r, c)])
				G[pos(r, c)] = label
				while que:
					(cr, cc) = que.popleft()
					for (dr, dc) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
						(nr, nc) = (cr + dr, cc + dc)
						if 0 <= nr < h and 0 <= nc < w and (s[nr][nc] == '.') and (G[pos(nr, nc)] == 0):
							G[pos(nr, nc)] = label
							que.append((nr, nc))
	start = pos(ch - 1, cw - 1)
	goal = pos(dh - 1, dw - 1)
	neighbors = [dr * W + dc for dc in range(-2, 3) for dr in range(-2, 3) if abs(dr) + abs(dc) > 0]
	used = [True] * (W * H)
	for r in range(h):
		for c in range(w):
			used[pos(r, c)] = s[r][c] == '#'
	que = deque([(start, 0)])
	label_dist_mapping = [-1] * (label + 1)
	used[start] = True
	label_dist_mapping[G[start]] = 0
	while que:
		(cpos, n) = que.popleft()
		if cpos == goal:
			return n
		for d in neighbors:
			npos = cpos + d
			if not used[npos]:
				used[npos] = True
				m = label_dist_mapping[G[npos]]
				if G[npos] == G[cpos] or n == m:
					que.appendleft((npos, n))
				else:
					label_dist_mapping[G[npos]] = n + 1
					que.append((npos, n + 1))
	return -1
(h, w) = list(map(int, input().split()))
(ch, cw) = list(map(int, input().split()))
(dh, dw) = list(map(int, input().split()))
s = [input() for i in range(h)]
print(solve(h, w, ch, cw, dh, dw, s))


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
A = []
for i in range(H):
	A.append([])
	s = input()
	for j in range(W):
		if s[j] == '.':
			A[-1].append(0)
		else:
			A[-1].append(1)
P = [[1000000.0 for i in range(W)] for j in range(H)]
P[Ch][Cw] = 0
D = deque([[Ch, Cw]])
while len(D):
	d = D.pop()
	for i in range(-2, 3):
		for j in range(-2, 3):
			if 0 <= d[0] + i < H and 0 <= d[1] + j < W and (A[d[0] + i][d[1] + j] == 0):
				if (i + j == 1 or i + j == -1) and i * j == 0 and (P[d[0]][d[1]] < P[d[0] + i][d[1] + j]):
					D.append([d[0] + i, d[1] + j])
					P[d[0] + i][d[1] + j] = P[d[0]][d[1]]
				elif P[d[0]][d[1]] + 1 < P[d[0] + i][d[1] + j]:
					D.appendleft([d[0] + i, d[1] + j])
					P[d[0] + i][d[1] + j] = P[d[0]][d[1]] + 1
if P[Dh][Dw] == 1000000.0:
	print(-1)
else:
	print(P[Dh][Dw])


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 _ in range(H)]

def BFS(maze, s, g):
	q1 = deque([s])
	checked = []
	cost = [[-1] * W for _ in range(H)]
	m = 0
	while q1:
		(h, w, n) = q1.popleft()
		if cost[h][w] < 0:
			cost[h][w] = n
			if (h, w) == g:
				return n
			dp = [(x - 2, y - 2) for x in range(5) for y in range(5) if x - 2 != 0 or y - 2 != 0]
			for (dh, dw) in dp:
				if 0 <= h + dh < H and 0 <= w + dw < W and (maze[h + dh][w + dw] == '.'):
					if (dh, dw) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
						q1.appendleft((h + dh, w + dw, n))
					else:
						q1.append((h + dh, w + dw, n + 1))
	return cost[g[0]][g[1]]
print(BFS(maze, (CH - 1, CW - 1, 0), (DH - 1, DW - 1)))


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 = [input() for _ in range(H)]
dist = [[float('inf') for _ in range(W)] for _ in range(H)]
dist[Ch][Cw] = 0
que = deque()
que.append((Ch, Cw))
while que:
	(i, j) = que.popleft()
	d = dist[i][j]
	for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
		if 0 <= ni < H and 0 <= nj < W:
			if S[ni][nj] == '.' and d < dist[ni][nj]:
				dist[ni][nj] = d
				que.appendleft((ni, nj))
	nd = d + 1
	for a in range(-2, 3):
		for b in range(-2, 3):
			(ni, nj) = (i + a, j + b)
			if 0 <= ni < H and 0 <= nj < W:
				if S[ni][nj] == '.' and nd < dist[ni][nj]:
					dist[ni][nj] = nd
					que.append((ni, nj))
if dist[Dh][Dw] == float('inf'):
	print(-1)
else:
	print(dist[Dh][Dw])


from collections import deque
(H, W) = map(int, input().split())
(CH, CW) = map(int, input().split())
(DH, DW) = map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
q = deque([(CH - 1, CW - 1, 0)])
while q:
	(h, w, c) = q.popleft()
	if S[h][w] == '.':
		S[h][w] = c
		for i in range(-2, 3):
			for j in range(-2, 3):
				if 0 <= h + i < H and 0 <= w + j < W and (S[h + i][w + j] == '.'):
					if abs(i) + abs(j) == 1:
						q.appendleft((h + i, w + j, c))
					elif abs(i) + abs(j) >= 2:
						q.append((h + i, w + j, c + 1))
if S[DH - 1][DW - 1] == '.':
	print(-1)
else:
	print(S[DH - 1][DW - 1])


from collections import deque
(H, W) = map(int, input().split())
C = tuple(map(lambda a: int(a) - 1, input().split()))
D = tuple(map(lambda a: int(a) - 1, input().split()))
S = [input() for _ in range(H)]
INF = 10 ** 18

def cord(h, w):
	return h * W + w
minDist = [INF] * (H * W + 10)
que = deque([(C, 0)])
minDist[cord(*C)] = 0
while que:
	((h, w), dist) = que.popleft()
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			(toH, toW) = (h + dh, w + dw)
			if not (0 <= toH < H and 0 <= toW < W) or (h, w) == (toH, toW):
				continue
			if S[toH][toW] == '#':
				continue
			d = 0 if abs(dh) + abs(dw) <= 1 else 1
			if minDist[cord(toH, toW)] > dist + d:
				minDist[cord(toH, toW)] = dist + d
				if d == 0:
					que.appendleft(((toH, toW), dist + d))
				else:
					que.append(((toH, toW), dist + d))
print(minDist[cord(*D)] if minDist[cord(*D)] < INF else -1)


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 = [0] * H
hoge = 0
for i in range(H):
	S[i] = [-1] * W
	hoge = input()
	for j in range(W):
		if hoge[j] == '.':
			S[i][j] = 10000000
DDD = [0] * 25
dddd = 0
for dx in (-2, -1, 0, 1, 2):
	for dy in (-2, -1, 0, 1, 2):
		DDD[dddd] = (dx, dy, dx * dx + dy * dy)
		dddd += 1
D = deque()
D.append((CH, CW, 0))
S[CH][CW] = 0
while len(D):
	(X, Y, DD) = D.pop()
	for (dx, dy, a) in DDD:
		XX = X + dx
		YY = Y + dy
		if a == 0 or not 0 <= XX < H or (not 0 <= YY < W) or (S[XX][YY] == -1):
			continue
		elif a == 1 and S[XX][YY] > DD:
			D.append((XX, YY, DD))
			S[XX][YY] = DD
		elif S[XX][YY] > DD + 1:
			D.appendleft((XX, YY, DD + 1))
			S[XX][YY] = DD + 1
print(-1 if S[DH][DW] == 10000000 else S[DH][DW])


from collections import deque

def main():
	(h, w) = map(int, input().split())
	(ch, cw) = map(int, input().split())
	(dh, dw) = map(int, input().split())
	base = ['#' * (w + 4)]
	base.append('#' * (w + 4))
	for n in range(h):
		base.append('##' + input() + '##')
	base.append('#' * (w + 4))
	base.append('#' * (w + 4))
	ans = [[-1] * (w + 4) for _ in range(h + 4)]
	for j in range(w + 4):
		for i in range(h + 4):
			if base[i][j] == '#':
				ans[i][j] = -2
	ch += 1
	cw += 1
	dh += 1
	dw += 1
	ans[ch][cw] = 0
	move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	move2 = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
	q = deque([[ch, cw]])
	one_time = deque([])
	while len(q) > 0:
		(x, y) = q.popleft()
		one_time.append([x, y])
		for (i, j) in move:
			(v1, v2) = (x + i, y + j)
			if ans[v1][v2] == -1:
				ans[v1][v2] = ans[x][y]
				q.append([v1, v2])
		if len(q) == 0:
			while len(one_time) > 0:
				(x2, y2) = one_time.popleft()
				for (i, j) in move2:
					(v1, v2) = (x2 + i, y2 + j)
					if ans[v1][v2] == -1:
						ans[v1][v2] = ans[x2][y2] + 1
						q.append([v1, v2])
	print(ans[dh][dw])

def __starting_point():
	main()
__starting_point()


from collections import deque
(H, W) = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = ['*' * (W + 4)] * (H + 4)
for x in range(H):
	S[x + 2] = '**' + input() + '**'
V = []
for a in range(-2, 3):
	for b in range(-2, 3):
		if not a == b == 0:
			if abs(a) + abs(b) <= 1:
				V.append(((a, b), 0))
			else:
				V.append(((a, b), 1))
inf = float('inf')
Dist = [[inf] * (W + 1) for _ in range(H + 1)]
Q = deque([C])
Dist[C[0]][C[1]] = 0
while Q:
	(x, y) = Q.popleft()
	for ((a, b), c) in V:
		try:
			if S[x + a + 1][y + b + 1] == '.' and Dist[x][y] + c < Dist[x + a][y + b]:
				Dist[x + a][y + b] = Dist[x][y] + c
				if c == 0:
					Q.appendleft((x + a, y + b))
				else:
					Q.append((x + a, y + b))
		except:
			pass
if Dist[D[0]][D[1]] < inf:
	print(Dist[D[0]][D[1]])
else:
	print(-1)


import sys
from collections import deque
sys.setrecursionlimit(500005)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
(h, w) = na()
(ch, cw) = na()
(dh, dw) = na()
b = []
for i in range(h):
	b.append(ns())
q = deque()
q.append((ch - 1, cw - 1))
ds = [9999999999] * (h * w)
ds[(ch - 1) * w + cw - 1] = 0
di = ((1, 0), (0, 1), (-1, 0), (0, -1))
while q:
	(r, c) = q.popleft()
	for k in di:
		(nr, nc) = (r + k[0], c + k[1])
		if 0 <= nr < h and 0 <= nc < w and (b[nr][nc] == '.') and (ds[nr * w + nc] > ds[r * w + c]):
			ds[nr * w + nc] = ds[r * w + c]
			q.appendleft((nr, nc))
	for nr in range(r - 2, r + 3):
		for nc in range(c - 2, c + 3):
			if 0 <= nr < h and 0 <= nc < w and (b[nr][nc] == '.') and (ds[nr * w + nc] > ds[r * w + c] + 1):
				ds[nr * w + nc] = ds[r * w + c] + 1
				q.append((nr, nc))
if ds[(dh - 1) * w + dw - 1] > 9999999:
	print(-1)
else:
	print(ds[(dh - 1) * w + dw - 1])


import heapq
(h, w) = map(int, input().split())
(sh, sw) = map(lambda x: int(x) - 1, input().split())
(gh, gw) = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10 ** 10
D = [[inf] * w for i in range(h)]
D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
	(_, (curr_h, curr_w)) = heapq.heappop(Q)
	for di in range(-2, 3):
		for dj in range(-2, 3):
			(next_h, next_w) = (curr_h + di, curr_w + dj)
			if 0 <= next_h < h and 0 <= next_w < w and (S[next_h][next_w] == '.'):
				nex = int(abs(di) + abs(dj) != 1)
				if D[next_h][next_w] > D[curr_h][curr_w] + nex:
					D[next_h][next_w] = D[curr_h][curr_w] + nex
					heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
	print(-1)
else:
	print(D[gh][gw])


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
coordinates = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(0, ch, cw)])
while que:
	(d, i, j) = que.popleft()
	if (i, j) == (dh, dw):
		print(d)
		exit()
	if visited[i][j]:
		continue
	visited[i][j] = True
	for (cdi, cdj) in coordinates:
		(ni, nj) = (i + cdi, j + cdj)
		if 0 <= ni < h and 0 <= nj < w and (s[ni][nj] == '.'):
			que.appendleft((d, ni, nj))
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if di == dj == 0:
				continue
			(ni, nj) = (i + di, j + dj)
			if 0 <= ni < h and 0 <= nj < w and (s[ni][nj] == '.') and (not visited[ni][nj]):
				que.append((d + 1, ni, nj))
print(-1)


(H, W) = map(int, input().split())
(CH, CW) = map(lambda x: int(x) - 1, input().split())
(DH, DW) = map(lambda x: int(x) - 1, input().split())
maze = [input() for i in range(H)]
di = [[-1 for _ in range(W)] for _ in range(H)]
adj = []
for i in range(-1, 2):
	for j in range(-1, 2):
		if i == 0 or j == 0:
			adj.append((i, j))
warp = []
for i in range(-2, 3):
	for j in range(-2, 3):
		if (i, j) not in adj:
			warp.append((i, j))
adj.remove((0, 0))
from collections import deque
dq = deque([(CH, CW, 0)])
while dq:
	(h, w, d) = dq.popleft()
	if 0 <= h < H and 0 <= w < W and (di[h][w] < 0) and (maze[h][w] == '.'):
		di[h][w] = d
	else:
		continue
	for i in range(len(adj)):
		dq.appendleft((h + adj[i][0], w + adj[i][1], d))
	for i in range(len(warp)):
		dq.append((h + warp[i][0], w + warp[i][1], d + 1))
print(di[DH][DW])


import queue
(h, w) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
s = [input() for _ in range(h)]
q = queue.deque([[sy - 1, sx - 1]])
q2 = [[sy - 1, sx - 1]]
q3 = []
inf = 10 ** 7
dist = [[inf for _ in range(w)] for _ in range(h)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dist[sy - 1][sx - 1] = 0
while q:
	(y, x) = q.pop()
	for (dy, dx) in d:
		(ny, nx) = (y + dy, x + dx)
		if 0 <= ny < h and 0 <= nx < w and (s[ny][nx] != '#') and (dist[ny][nx] == inf):
			dist[ny][nx] = min(dist[y][x], dist[ny][nx])
			q.append([ny, nx])
			q2.append([ny, nx])
	if not q:
		for (y, x) in q2:
			for dy in range(-2, 3):
				for dx in range(-2, 3):
					(ny, nx) = (y + dy, x + dx)
					if 0 <= ny < h and 0 <= nx < w and (s[ny][nx] != '#') and (dist[ny][nx] == inf):
						dist[ny][nx] = min(dist[y][x] + 1, dist[ny][nx])
						q.append([ny, nx])
						q3.append([ny, nx])
		q2 = q3
		q3 = []
print(dist[gy - 1][gx - 1] if dist[gy - 1][gx - 1] != inf else -1)


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(lambda x: int(x) - 1, input().split())
(dh, dw) = map(lambda x: int(x) - 1, input().split())
G = []
for i in range(h):
	G.append(list(input()))
queue = deque([(ch, cw)])
S = [[float('inf')] * w for _ in range(h)]
S[ch][cw] = 0
while queue:
	(y, x) = queue.popleft()
	dx_dy = ((1, 0), (0, 1), (-1, 0), (0, -1))
	ans = S[y][x]
	if (y, x) == (dh, dw):
		S[y][x] = ans
		break
	for (j, i) in dx_dy:
		if 0 <= x + i < w and 0 <= y + j < h and (S[y + j][x + i] > ans) and (G[y + j][x + i] == '.'):
			queue.appendleft((y + j, x + i))
			S[y + j][x + i] = ans
	ans += 1
	for i in range(-2, 3):
		for j in range(-2, 3):
			if 0 <= x + i < w and 0 <= y + j < h and (S[y + j][x + i] > ans) and (G[y + j][x + i] == '.'):
				S[y + j][x + i] = ans
				queue.append((y + j, x + i))
if S[dh][dw] == float('inf'):
	print(-1)
else:
	print(S[dh][dw])


import sys
input = sys.stdin.readline

def solve():
	dxys = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	(H, W) = list(map(int, input().split()))
	(Ch, Cw) = list(map(int, input().split()))
	(Dh, Dw) = list(map(int, input().split()))
	Sss = ['#' * (W + 4)] + ['#' * (W + 4)] + ['##' + input().rstrip() + '##' for _ in range(H)] + ['#' * (W + 4)] + ['#' * (W + 4)]
	(Ch, Cw, Dh, Dw) = (Ch + 1, Cw + 1, Dh + 1, Dw + 1)
	usedss = [[0] * (W + 4) for _ in range(H + 4)]
	for x in range(H + 4):
		for y in range(W + 4):
			if Sss[x][y] == '#':
				usedss[x][y] = 1
	ans = 0
	vs = set([(Ch, Cw)])
	vNews = set([(Ch, Cw)])
	usedss[Ch][Cw] = 1
	while True:
		while vs:
			v2s = set()
			for (x, y) in vs:
				for (dx, dy) in dxys:
					(x2, y2) = (x + dx, y + dy)
					if usedss[x2][y2]:
						continue
					v2s.add((x2, y2))
					vNews.add((x2, y2))
					usedss[x2][y2] = 1
			vs = v2s
		if usedss[Dh][Dw]:
			print(ans)
			break
		if not vNews:
			print(-1)
			break
		vs = set()
		for (x, y) in vNews:
			for dx in range(-2, 3):
				for dy in range(-2, 3):
					(x2, y2) = (x + dx, y + dy)
					if usedss[x2][y2]:
						continue
					vs.add((x2, y2))
					usedss[x2][y2] = 1
		ans += 1
		vNews = set(vs)
solve()


import heapq
(H, W) = map(lambda x: int(x) + 4, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
grid = '#' * W * 2
for _ in range(H - 4):
	grid += '##' + input() + '##'
grid += '#' * W * 2
move_list = []
for i in range(5):
	for j in range(5):
		if (i, j) == (2, 2):
			continue
		elif (i, j) == (1, 2) or (i, j) == (2, 1) or (i, j) == (2, 3) or ((i, j) == (3, 2)):
			move_list.append((0, i - 2 + W * (j - 2)))
		else:
			move_list.append((1, i - 2 + W * (j - 2)))

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq)
	cost = [float('inf')] * (H * W)
	cost[s] = 0
	while hq:
		(c, v) = heapq.heappop(hq)
		if c > cost[v]:
			continue
		for (dc, dv) in move_list:
			w = v + dv
			tmp = cost[v] + dc
			if grid[w] == '#':
				continue
			if tmp < cost[w]:
				cost[w] = tmp
				heapq.heappush(hq, (tmp, w))
	return cost
ans = dijkstra((Ch + 1) * W + Cw + 1)[(Dh + 1) * W + Dw + 1]
if ans == float('inf'):
	print(-1)
else:
	print(ans)


(h, w) = map(int, input().split())
s = list(map(int, input().split()))
g = list(map(int, input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
	tmp = input()
	raw.append(tmp)
	t = []
	for j in range(w):
		if tmp[j] == '.':
			t.append(0)
		else:
			t.append(1)
	seen.append(t)
now = [s]
ans = 0

def check(ii, jj):
	if 0 <= ii < h and 0 <= jj < w:
		if seen[ii][jj] == 0:
			seen[ii][jj] = 1
			now.append([ii, jj])
while now:
	for x in now:
		(a, b) = x
		check(a - 1, b)
		check(a + 1, b)
		check(a, b - 1)
		check(a, b + 1)
	if seen[g[0]][g[1]] == 1:
		print(ans)
		break
	ans += 1
	last = now
	now = []
	for x in last:
		(a, b) = x
		for di in range(-2, 3):
			for dj in range(-2, 3):
				check(a + di, b + dj)
else:
	print(-1)


from collections import deque
(H, W) = [int(i) for i in input().split()]
(ch, cw) = [int(i) - 1 for i in input().split()]
(dh, dw) = [int(i) - 1 for i in input().split()]
S = [input() for i in range(H)]
cost = [[-1] * W for i in range(H)]
q = [[0, ch, cw]]
q = deque(q)
ans = -1
while q:
	(cnt, cx, cy) = q.popleft()
	if cost[cx][cy] < 0:
		cost[cx][cy] = cnt
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				if 0 <= cx + dx < H and 0 <= cy + dy < W and (S[cx + dx][cy + dy] == '.'):
					if cost[cx + dx][cy + dy] < 0:
						if [dx, dy] in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
							q.appendleft([cnt, cx + dx, cy + dy])
						else:
							q.append([cnt + 1, cx + dx, cy + dy])
print(cost[dh][dw])


from collections import *
I = 9 ** 9
((h, w), (s, t), (f, g)) = eval('map(int,input().split()),' * 3)
(m, d) = zip(*eval('(input(),[I]*w),' * h))
q = deque([(s - 1, t - 1, 1)])
r = range(-2, 3)
while q:
	(y, x, c) = q.popleft()
	if d[y][x] > c:
		for a in r:
			for b in r:
				i = a + y
				j = b + x
				d[y][x] = c
				h > i > -1 < j < w != m[i][j] > '#' != (abs(a) + abs(b) < 2 != q.appendleft((i, j, c)), q.append((i, j, c + 1)))
print(d[f - 1][g - 1] % I - 1)


from collections import deque

def solve():
	(H, W) = list(map(int, input().split()))
	(CH, CW) = list(map(int, input().split()))
	(DH, DW) = list(map(int, input().split()))
	S = ['##' + input() + '##' for _ in range(H)]
	for i in range(2):
		S.insert(0, '#' * (W + 4))
		S.append('#' * (W + 4))
	inf = int(1000000000.0)
	cost = [[inf for _ in range(W + 4)] for _ in range(H + 4)]
	cost0 = deque()
	ans = -1
	cost0.append((CH + 1, CW + 1, 0))
	cost[CH + 1][CW + 1] = 0
	move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move]
	cost1 = deque()
	while cost0:
		(h, w, c) = cost0.popleft()
		cost1.append((h, w, c))
		for (i, j) in move:
			dh = h + i
			dw = w + j
			if S[dh][dw] == '.' and c < cost[dh][dw]:
				cost[dh][dw] = c
				cost0.appendleft((dh, dw, cost[dh][dw]))
		if len(cost0) == 0:
			while cost1:
				(h, w, c) = cost1.popleft()
				for (i, j) in warp:
					dh = h + i
					dw = w + j
					if S[dh][dw] == '.' and c + 1 < cost[dh][dw]:
						cost[dh][dw] = c + 1
						cost0.append((dh, dw, cost[dh][dw]))
		if cost[DH + 1][DW + 1] != inf:
			ans = cost[DH + 1][DW + 1]
	print(ans)

def __starting_point():
	solve()
__starting_point()


(H, W) = map(int, input().split())
start = tuple(map(lambda x: x - 1, map(int, input().split())))
goal = tuple(map(lambda x: x - 1, map(int, input().split())))
S = [input() for i in range(H)]
from collections import deque
q = deque([])
q.append([start[0], start[1], 0])
INF = 10 ** 10
cost = [[INF] * W for i in range(H)]
while q:
	(y, x, c) = q.popleft()
	if S[y][x] == '#':
		continue
	if cost[y][x] <= c:
		continue
	cost[y][x] = c
	for i in range(-2, 3):
		for j in range(-2, 3):
			if i == 0 and j == 0:
				continue
			if 0 <= y + i < H and 0 <= x + j < W:
				if abs(i) + abs(j) == 1:
					q.appendleft([y + i, x + j, c])
				else:
					q.append([y + i, x + j, c + 1])
if cost[goal[0]][goal[1]] == INF:
	print(-1)
else:
	print(cost[goal[0]][goal[1]])


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
pathA = [(1, 0), (0, 1), (-1, 0), (0, -1)]
pathB = []
for n in range(5):
	for m in range(5):
		pathB.append((n - 2, m - 2))
visited = [[-1] * W for _ in range(H)]
queue = deque([])
queue.append((ch - 1, cw - 1, 0))
while queue:
	(h, w, d) = queue.popleft()
	if visited[h][w] == -1:
		visited[h][w] = d
		for (h1, w1) in pathA:
			newh = h1 + h
			neww = w1 + w
			if newh >= 0 and newh < H and (neww >= 0) and (neww < W) and (S[newh][neww] == '.'):
				queue.appendleft((newh, neww, d))
		for (h1, w1) in pathB:
			newh = h1 + h
			neww = w1 + w
			if newh >= 0 and newh < H and (neww >= 0) and (neww < W) and (S[newh][neww] == '.'):
				queue.append((newh, neww, d + 1))
print(visited[dh - 1][dw - 1])


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
(ch, cw, dh, dw) = (ch - 1, cw - 1, dh - 1, dw - 1)
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(H)]
que = deque([[cw, ch, 0]])
while que:
	(x, y, cost) = que.popleft()
	if d[y][x] == -1 or d[y][x] > cost:
		d[y][x] = cost
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < W and 0 <= ny < H and (s[ny][nx] != '#'):
					if abs(dx) + abs(dy) == 1:
						que.appendleft([nx, ny, cost])
					else:
						que.append([nx, ny, cost + 1])
print(d[dh][dw])


(h, w) = map(int, input().split())
s = list(map(int, input().split()))
g = list(map(int, input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
	tmp = input()
	raw.append(tmp)
	t = []
	for j in range(w):
		if tmp[j] == '.':
			t.append(0)
		else:
			t.append(1)
	seen.append(t)
now = [s]
ans = 0

def check(ii, jj):
	if 0 <= ii < h and 0 <= jj < w:
		if seen[ii][jj] == 0:
			seen[ii][jj] = 1
			now.append([ii, jj])
seen[s[0]][s[1]] = 1
from collections import deque
now = deque([s])
while now:
	for i in range(10 ** 6):
		try:
			(a, b) = now[i]
			check(a - 1, b)
			check(a + 1, b)
			check(a, b - 1)
			check(a, b + 1)
		except:
			break
	if seen[g[0]][g[1]] == 1:
		print(ans)
		break
	ans += 1
	last = now
	now = deque()
	for x in last:
		(a, b) = x
		for di in range(-2, 3):
			for dj in range(-2, 3):
				check(a + di, b + dj)
else:
	print(-1)


from collections import deque

def main():
	(h, w) = list(map(int, input().split()))
	(start_h, start_w) = [int(x) + 1 for x in input().split()]
	(goal_h, goal_w) = [int(x) + 1 for x in input().split()]
	s = ['#' * (w + 4)]
	s.append('#' * (w + 4))
	for _ in range(h):
		s.append('##' + input() + '##')
	s.append('#' * (w + 4))
	s.append('#' * (w + 4))
	ans = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if s[i][j] == '#':
				ans[i][j] = -2
	ans[start_h][start_w] = 0
	move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
	yet = deque([(start_h, start_w)])
	done = deque()
	while yet:
		(x1, y1) = yet.popleft()
		done.append((x1, y1))
		for (p, q) in move1:
			(v1, v2) = (x1 + p, y1 + q)
			if ans[v1][v2] == -1:
				yet.append((v1, v2))
				ans[v1][v2] = ans[x1][y1]
		if len(yet) == 0:
			while done:
				(x2, y2) = done.popleft()
				for (p, q) in move2:
					(i, j) = (x2 + p, y2 + q)
					if ans[i][j] == -1:
						ans[i][j] = ans[x2][y2] + 1
						yet.append((i, j))
	print(ans[goal_h][goal_w])

def __starting_point():
	main()
__starting_point()


def main():
	from collections import deque
	(h, w) = map(int, input().split())
	start = tuple(map(lambda x: int(x) - 1, input().split()))
	goal = tuple(map(lambda x: int(x) - 1, input().split()))
	maze = tuple([tuple(input()) for _ in range(h)])
	vis = [[False] * w for _ in range(h)]
	mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	mj = list(set(((i, j) for i in range(-2, 3) for j in range(-2, 3))) - set(mw) - {(0, 0)})
	q = deque()
	q.append((start[0], start[1], 0))
	while q:
		(y, x, c) = q.popleft()
		if not (0 <= y < h and 0 <= x < w) or vis[y][x] or maze[y][x] == '#':
			continue
		vis[y][x] = True
		if (y, x) == goal:
			print(c)
			break
		for (a, b) in mw:
			q.appendleft((y + a, x + b, c))
		for (a, b) in mj:
			q.append((y + a, x + b, c + 1))
	else:
		print(-1)
main()


import heapq
(h, w) = map(int, input().split())
(i0, j0) = map(lambda x: int(x) - 1, input().split())
(i1, j1) = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10 ** 10
D = [[inf] * w for i in range(h)]
D[i0][j0] = 0
Q = [(0, (i0, j0))]
heapq.heapify(Q)
while Q:
	(_, (i, j)) = heapq.heappop(Q)
	for di in range(-2, 3):
		for dj in range(-2, 3):
			(ii, jj) = (i + di, j + dj)
			if 0 <= ii < h and 0 <= jj < w and (S[ii][jj] == '.'):
				nex = int(abs(di) + abs(dj) != 1)
				if D[i][j] + nex < D[ii][jj]:
					D[ii][jj] = D[i][j] + nex
					heapq.heappush(Q, (D[ii][jj], (ii, jj)))
if D[i1][j1] >= inf:
	print(-1)
else:
	print(D[i1][j1])


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.appendleft([x + dx[i], y + dy[i]])
					ans[y + dy[i]][x + dx[i]] = ans[y][x]
					count += 1
		if count != 4:
			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])


from collections import *
INF = 10 ** 18
(h, w) = map(int, input().split())
(sh, sw) = map(int, input().split())
(gh, gw) = map(int, input().split())
s = [input() for _ in range(h)]
q = deque([(sh - 1, sw - 1, 0)])
d = [[INF] * w for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
wx = [-2, -1, 0, 1, 2]
wy = [-2, -1, 0, 1, 2]
while q:
	(x, y, c) = q.popleft()
	if d[x][y] != INF:
		continue
	d[x][y] = c
	for (i, j) in zip(dx, dy):
		nx = x + i
		ny = y + j
		if not (0 <= nx < h and 0 <= ny < w):
			continue
		if s[nx][ny] == '.' and d[nx][ny] == INF:
			q.appendleft((nx, ny, c))
	for i in wx:
		nx = x + i
		if not 0 <= nx < h:
			continue
		for j in wy:
			ny = y + j
			if not 0 <= ny < w:
				continue
			if s[nx][ny] == '.' and d[nx][ny] == INF:
				q.append((nx, ny, c + 1))
print(d[gh - 1][gw - 1] if d[gh - 1][gw - 1] != INF else -1)


from collections import deque

def main():
	(h, w) = list(map(int, input().split()))
	c = list([int(x) + 1 for x in input().split()])
	d = list([int(x) + 1 for x in input().split()])
	s = ['#' * (w + 4)] * 2 + ['#' * 2 + input() + '#' * 2 for _ in range(h)] + ['#' * (w + 4)] * 2
	ans = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if s[i][j] == '#':
				ans[i][j] = -2
	ans[c[0]][c[1]] = 0
	move1 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	move2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i) + abs(j) > 1]
	yet = deque([(c[0], c[1])])
	done = deque()
	while yet:
		(y, x) = yet.popleft()
		done.append((y, x))
		for (dy, dx) in move1:
			(ydy, xdx) = (y + dy, x + dx)
			if ans[ydy][xdx] == -1:
				yet.append((ydy, xdx))
				ans[ydy][xdx] = ans[y][x]
		if len(yet) == 0:
			while done:
				(y, x) = done.popleft()
				for (dy, dx) in move2:
					(ydy, xdx) = (y + dy, x + dx)
					if ans[ydy][xdx] == -1:
						ans[ydy][xdx] = ans[y][x] + 1
						yet.append((ydy, xdx))
	print(ans[d[0]][d[1]])

def __starting_point():
	main()
__starting_point()


(H, W) = map(int, input().split())
(sh, sw) = map(lambda x: int(x) - 1, input().split())
(eh, ew) = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]
INF = 10 ** 9
dst = [[INF] * W for _ in range(H)]
dst[sh][sw] = 0
from collections import deque
dq = deque([(sh, sw)])
while dq:
	(h, w) = dq.popleft()
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			nh = h + dh
			nw = w + dw
			if dh * dh + dw * dw == 1:
				if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (dst[h][w] < dst[nh][nw]):
					dst[nh][nw] = dst[h][w]
					dq.appendleft((nh, nw))
			elif dh * dh + dw * dw > 1:
				if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (dst[h][w] + 1 < dst[nh][nw]):
					dst[nh][nw] = dst[h][w] + 1
					dq.append((nh, nw))
print(-1 if dst[eh][ew] == INF else dst[eh][ew])


(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
	for j in range(-2, 3):
		if abs(i) + abs(j) < 2:
			continue
		vec5 += [(i, j)]
c = 0
q = [(ch, cw)]
while len(q) > 0:
	nq = []
	while len(q) > 0:
		(i, j) = q.pop()
		s[i][j] = c
		nq += [(i, j)]
		for v in vec:
			ii = i + v[0]
			jj = j + v[1]
			if 0 <= ii < h and 0 <= jj < w and (s[ii][jj] == '.'):
				q += [(ii, jj)]
	while len(nq) > 0:
		(i, j) = nq.pop()
		for v in vec5:
			ii = i + v[0]
			jj = j + v[1]
			if 0 <= ii < h and 0 <= jj < w and (s[ii][jj] == '.'):
				q += [(ii, jj)]
	c += 1
if s[dh][dw] == '.':
	print(-1)
else:
	print(s[dh][dw])


import collections
(R, C) = map(int, input().split())
(sy, sx) = map(lambda n: int(n) - 1, input().split())
(gy, gx) = map(lambda n: int(n) - 1, input().split())
c = [input() for _ in range(R)]
dist = [[-1 for _ in range(C)] for _ in range(R)]
q = collections.deque([(sy, sx, -1)])
G = [(-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)]
while q:
	(y, x, d) = q.popleft()
	if y < 0 or R <= y or x < 0 or (C <= x):
		continue
	if c[y][x] == '#':
		continue
	if dist[y][x] != -1:
		continue
	dist[y][x] = d + 1
	for (i, j) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
		q.appendleft((y + i, x + j, d))
	for (i, j) in G:
		q.append((y + i, x + j, d + 1))
print(dist[gy][gx])


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(lambda x: int(x) - 1, input().split())
(dh, dw) = map(lambda x: int(x) - 1, input().split())
S = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
move = []
for i in range(-2, 3):
	for j in range(-2, 3):
		if i == 0 and j == 0:
			continue
		move.append((i, j))
q = deque()
q.append((0, ch, cw))
while q:
	(c, h, w) = q.popleft()
	if dist[h][w] >= 0:
		continue
	dist[h][w] = c
	for (hh, ww) in move:
		if 0 <= h + hh < H and 0 <= w + ww < W and (S[h + hh][w + ww] == '.') and (dist[h + hh][w + ww] < 0):
			if (hh, ww) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
				q.appendleft((c, h + hh, w + ww))
			else:
				q.append((c + 1, h + hh, w + ww))
print(dist[dh][dw])


from collections import deque

def main():
	(h, w) = list(map(int, input().split()))
	(ch, cw) = list(map(int, input().split()))
	(dh, dw) = list(map(int, input().split()))
	base = ['#' * (w + 4)]
	base.append('#' * (w + 4))
	for n in range(h):
		base.append('##' + input() + '##')
	base.append('#' * (w + 4))
	base.append('#' * (w + 4))
	ans = [[-1] * (w + 4) for _ in range(h + 4)]
	for i in range(h + 4):
		for j in range(w + 4):
			if base[i][j] == '#':
				ans[i][j] = -2
	ch += 1
	cw += 1
	dh += 1
	dw += 1
	ans[ch][cw] = 0
	move1 = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	move2 = [[-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]]
	q1 = deque([[ch, cw]])
	q2 = deque([])
	while q1:
		(x1, y1) = q1.popleft()
		q2.append([x1, y1])
		for (i, j) in move1:
			(nx, ny) = (x1 + i, y1 + j)
			if ans[nx][ny] == -1:
				ans[nx][ny] = ans[x1][y1]
				q1.append([nx, ny])
		if len(q1) == 0:
			while q2:
				(x2, y2) = q2.popleft()
				for (i, j) in move2:
					(mx, my) = (x2 + i, y2 + j)
					if ans[mx][my] == -1:
						ans[mx][my] = ans[x2][y2] + 1
						q1.append([mx, my])
	print(ans[dh][dw])

def __starting_point():
	main()
__starting_point()


from collections import deque
(h, w) = map(int, input().split())
(cx, cy) = map(int, input().split())
cx += 1
cy += 1
(dx, dy) = map(int, input().split())
dx += 1
dy += 1
l = []
l.append('#' * (w + 4))
l.append('#' * (w + 4))
for i in range(h):
	l.append('##' + input() + '##')
l.append('#' * (w + 4))
l.append('#' * (w + 4))
q = deque([[cx, cy]])
qq = deque([[cx, cy]])
s = [[-1 for i in j] for j in l]
s[cx][cy] = 0
while len(qq) > 0:
	while len(q) > 0:
		(x, y) = q.popleft()
		for (px, py) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
			if l[x + px][py + y] == '.' and s[x + px][y + py] == -1:
				s[x + px][y + py] = s[x][y]
				q.appendleft([x + px, y + py])
				qq.append([x + px, y + py])
	(x, y) = qq.popleft()
	for px in range(-2, 3):
		for py in range(-2, 3):
			if l[x + px][py + y] == '.' and s[x + px][y + py] == -1:
				s[x + px][y + py] = s[x][y] + 1
				q.append([x + px, y + py])
				qq.append([x + px, y + py])
print(s[dx][dy])


from collections import deque

def main():
	from sys import stdin
	readline = stdin.readline
	from builtins import max, min, range
	INF = 10 ** 6
	(H, W) = list(map(int, readline().split()))
	(C1, C2) = [int(x) - 1 for x in readline().split()]
	(D1, D2) = [int(x) - 1 for x in readline().split()]
	S = [readline()[:-1] for _ in range(H)]
	t = [[INF] * W for _ in range(H)]
	for h in range(H):
		Sh = S[h]
		th = t[h]
		for w in range(W):
			if Sh[w] == '#':
				th[w] = -1
	q = deque([(C1, C2)])
	a = 0
	t[C1][C2] = a
	while q:
		warpq = []
		while q:
			(h, w) = q.popleft()
			warpq.append((h, w))
			if 0 < h and t[h - 1][w] > a:
				t[h - 1][w] = a
				q.append((h - 1, w))
			if H - 1 > h and t[h + 1][w] > a:
				t[h + 1][w] = a
				q.append((h + 1, w))
			if 0 < w and t[h][w - 1] > a:
				t[h][w - 1] = a
				q.append((h, w - 1))
			if w < W - 1 and t[h][w + 1] > a:
				t[h][w + 1] = a
				q.append((h, w + 1))
		if t[D1][D2] != INF:
			break
		a += 1
		for (h, w) in warpq:
			for i in range(max(0, h - 2), min(H, h + 3)):
				ti = t[i]
				for j in range(max(0, w - 2), min(W, w + 3)):
					if ti[j] > a:
						ti[j] = a
						q.append((i, j))
	if t[D1][D2] == INF:
		print(-1)
	else:
		print(t[D1][D2])
main()


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
INF = 10 ** 7
queue = deque()
cost = [[INF] * w for _ in range(h)]
cost[ch - 1][cw - 1] = 0
dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
warp = []
for m in range(-2, 3):
	for n in range(-2, 3):
		if [m, n] not in [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]]:
			warp += [[m, n]]
queue.append([ch - 1, cw - 1, 0])
while queue:
	(x, y, d) = queue.popleft()
	if d > cost[x][y]:
		continue
	for (dx, dy) in dxdy:
		(nx, ny) = (x + dx, y + dy)
		if -1 < nx < h and -1 < ny < w and (s[nx][ny] != '#') and (d < cost[nx][ny]):
			cost[nx][ny] = d
			queue.appendleft([nx, ny, d])
	for (dx, dy) in warp:
		(nx, ny) = (x + dx, y + dy)
		if -1 < nx < h and -1 < ny < w and (s[nx][ny] != '#') and (d + 1 < cost[nx][ny]):
			cost[nx][ny] = d + 1
			queue.append([nx, ny, d + 1])
if cost[dh - 1][dw - 1] < INF:
	print(cost[dh - 1][dw - 1])
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = [int(i) - 1 for i in input().split()]
(dh, dw) = [int(i) - 1 for i in input().split()]
maze = []
for _ in range(H):
	a = input()
	maze.append(a)
d = deque([(ch, cw, 0)])
value = [[-1 for _ in range(W)] for _ in range(H)]
while d:
	(h, w, v) = d.popleft()
	if value[h][w] == -1:
		value[h][w] = v
		for hi in range(-2, 3):
			for wi in range(-2, 3):
				next_h = h + hi
				next_w = w + wi
				if (0 <= next_h < H) & (0 <= next_w < W):
					if maze[next_h][next_w] == '.':
						if (abs(hi) + abs(wi) == 1) & (value[next_h][next_w] == -1):
							d.appendleft((next_h, next_w, v))
						elif (abs(hi) + abs(wi) > 1) & (value[next_h][next_w] == -1):
							d.append((next_h, next_w, v + 1))
	else:
		continue
print(value[dh][dw])


from collections import deque

def solve():
	(H, W) = map(int, input().split())
	C = list(map(int, input().split()))
	D = list(map(int, input().split()))
	S = ['##' + input() + '##' for _ in range(H)]
	for i in range(2):
		S.insert(0, '#' * (W + 4))
		S.append('#' * (W + 4))
	INF = float('inf')
	cost = [[INF for _ in range(W + 4)] for _ in range(H + 4)]
	cost0 = deque()
	ans = -1
	cost0.append((C[0] + 1, C[1] + 1, 0))
	cost[C[0] + 1][C[1] + 1] = 0
	move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move]
	cost1 = deque()
	while cost0:
		(h, w, c) = cost0.popleft()
		cost1.append((h, w, c))
		for (i, j) in move:
			dh = h + i
			dw = w + j
			if S[dh][dw] == '.' and c < cost[dh][dw]:
				cost[dh][dw] = c
				cost0.appendleft((dh, dw, cost[dh][dw]))
		if len(cost0) == 0:
			while cost1:
				(h, w, c) = cost1.popleft()
				for (i, j) in warp:
					dh = h + i
					dw = w + j
					if S[dh][dw] == '.' and c + 1 < cost[dh][dw]:
						cost[dh][dw] = c + 1
						cost0.append((dh, dw, cost[dh][dw]))
		if cost[D[0] + 1][D[1] + 1] != INF:
			ans = cost[D[0] + 1][D[1] + 1]
	print(ans)

def __starting_point():
	solve()
__starting_point()


from collections import deque

def main():
	(H, W) = map(int, input().split())
	(Ch, Cw) = map(int, input().split())
	(Dh, Dw) = map(int, input().split())
	S = [input() for _ in range(H)]
	Q = deque([[Ch - 1, Cw - 1, 0]])
	cost = [[-1 for _ in range(W)] for _ in range(H)]
	while Q:
		(r, c, cnt) = Q.popleft()
		if cost[r][c] != -1:
			continue
		cost[r][c] = cnt
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr = r + dr
				nc = c + dc
				if 0 <= nr < H and 0 <= nc < W and (S[nr][nc] == '.'):
					if abs(dr) + abs(dc) == 1:
						Q.appendleft([nr, nc, cnt])
					elif abs(dr) + abs(dc) >= 2:
						Q.append([nr, nc, cnt + 1])
	print(cost[Dh - 1][Dw - 1])
main()


from collections import deque
number = list(map(int, input().split()))
(H, W) = (number[0], number[1])
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [str(input()) for i in range(H)]
INF = 10 ** 9
dp = [[INF] * W for i in range(H)]
trans_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
trans_b = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + trans_a]
Q = deque()
t = 0
C.append(t)
Q.append((C[0] - 1, C[1] - 1, C[2]))
dp[C[0] - 1][C[1] - 1] = t
while Q:
	(x, y, t) = (Q[0][0], Q[0][1], Q[0][2])
	Q.popleft()
	for (dx, dy) in trans_a:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] != '#') and (dp[nx][ny] > t):
			dp[nx][ny] = t
			Q.appendleft((nx, ny, t))
	for (dx, dy) in trans_b:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] != '#') and (dp[nx][ny] > t + 1):
			dp[nx][ny] = t + 1
			Q.append((nx, ny, t + 1))
if dp[D[0] - 1][D[1] - 1] == INF:
	print(-1)
else:
	print(dp[D[0] - 1][D[1] - 1])


(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
S = [input() for _ in range(H)]
A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch - 1][Cw - 1] = 0

def isValid(h, w):
	if h >= 0 and h < H and (w >= 0) and (w < W) and (S[h][w] == '.') and (A[h][w] == -1):
		return True
	else:
		return False
warp = 0
BFS_now = [(Ch - 1, Cw - 1)]
BFS_search = [(Ch - 1, Cw - 1)]
ij = [(-1, 0), (0, -1), (0, 1), (1, 0)]
while len(BFS_now) > 0:
	while len(BFS_search) > 0:
		BFS_search_tmp = []
		for (h, w) in BFS_search:
			for (i, j) in ij:
				if isValid(h + i, w + j):
					BFS_search_tmp.append((h + i, w + j))
					A[h + i][w + j] = warp
		BFS_now += BFS_search_tmp
		BFS_search = BFS_search_tmp
	BFS_now_tmp = []
	for (h, w) in BFS_now:
		for i in range(-2, 3):
			for j in range(-2, 3):
				if isValid(h + i, w + j):
					BFS_now_tmp.append((h + i, w + j))
					A[h + i][w + j] = warp + 1
	BFS_now = BFS_now_tmp
	BFS_search = BFS_now_tmp
	warp += 1
print(A[Dh - 1][Dw - 1])


from collections import deque
queue = deque()
(H, W) = [int(v) for v in input().split()]
(ch, cw) = [int(v) for v in input().split()]
(dh, dw) = [int(v) for v in input().split()]
S = [input() for _ in range(H)]
visited = [[-1 for _ in range(W)] for _ in range(H)]
queue.append((cw - 1, ch - 1, 0))

def check(x, y):
	return x > -1 and x < W and (y > -1) and (y < H) and (S[y][x] != '#') and (visited[y][x] == -1)
while len(queue) != 0:
	(x, y, c) = queue.popleft()
	if visited[y][x] != -1:
		continue
	visited[y][x] = c
	for d in [1, -1]:
		if check(x + d, y):
			queue.appendleft([x + d, y, c])
		if check(x, y + d):
			queue.appendleft([x, y + d, c])
	for dx in [-2, -1, 0, 1, 2]:
		for dy in [-2, -1, 0, 1, 2]:
			if check(x + dx, y + dy):
				queue.append((x + dx, y + dy, c + 1))
print(visited[dh - 1][dw - 1])


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [list(input()) for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
	maze = [[-1] * w for i in range(h)]
	maze[ch - 1][cw - 1] = 0
	qu = deque([])
	qu.append((cw - 1, ch - 1))
	magic = 0
	while qu:
		(x, y) = qu.popleft()
		for i in range(x - 2, x + 3):
			for j in range(y - 2, y + 3):
				nx = i
				ny = j
				if 0 <= nx <= w - 1 and 0 <= ny <= h - 1 and (s[ny][nx] == '.') and (maze[ny][nx] == -1 or maze[ny][nx] > maze[y][x] + 1):
					qu.append((nx, ny))
					maze[ny][nx] = maze[y][x] + 1
		for i in range(4):
			nx = dx[i] + x
			ny = dy[i] + y
			if 0 <= nx <= w - 1 and 0 <= ny <= h - 1 and (s[ny][nx] == '.') and (maze[ny][nx] == -1 or maze[ny][nx] > maze[y][x]):
				qu.appendleft((nx, ny))
				maze[ny][nx] = maze[y][x]
	return maze
maze = bfs()
print(maze[dh - 1][dw - 1])


from collections import deque
import sys
INF = 10 ** 8
(H, W) = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
MAP = []
for _ in range(H):
	MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
Q = deque()
Q.append([C[0] - 1, C[1] - 1, 0])
while len(Q) != 0:
	(x, y, cnt) = Q.popleft()
	if x == D[0] - 1 and y == D[1] - 1:
		print(cnt)
		sys.exit()
	for i in range(4):
		nx = x + tx[i]
		ny = y + ty[i]
		if 0 <= nx < H and 0 <= ny < W and (MAP[nx][ny] == '.') and (d[nx][ny] > cnt):
			d[nx][ny] = cnt
			Q.appendleft([nx, ny, cnt])
	for (i, j) in tx_y:
		nx = x + i
		ny = y + j
		if 0 <= nx < H and 0 <= ny < W and (MAP[nx][ny] == '.') and (d[nx][ny] > cnt + 1):
			d[nx][ny] = cnt + 1
			Q.append([nx, ny, cnt + 1])
print(-1)


import collections
import sys
input = sys.stdin.readline
(h, w) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
board = [['#'] * (w + 2)] + [list('#' + input().replace('\n', '') + '#') for _ in range(h)] + [['#'] * (w + 2)]
scores = [[10 ** 18] * (w + 2) for _ in range(h + 2)]
scores[sy][sx] = 0
q = collections.deque()
q.append((sy, sx))
count = 0
while len(q) != 0:
	(y, x) = q.popleft()
	for (dx, dy) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
		if 1 <= x + dx <= w and 1 <= y + dy <= h and (board[y + dy][x + dx] != '#') and (scores[y + dy][x + dx] > scores[y][x]):
			scores[y + dy][x + dx] = scores[y][x]
			q.appendleft((y + dy, x + dx))
	for dy in range(-2, 3):
		for dx in range(-2, 3):
			if dx == 0 and dy == 0:
				continue
			if 1 <= x + dx <= w and 1 <= y + dy <= h and (board[y + dy][x + dx] != '#') and (scores[y + dy][x + dx] > scores[y][x] + 1):
				scores[y + dy][x + dx] = scores[y][x] + 1
				q.append((y + dy, x + dx))
if scores[gy][gx] == 10 ** 18:
	print(-1)
else:
	print(scores[gy][gx])


(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 i in range(h)]
cost = [[-1] * w for i in range(h)]
from collections import deque
q = [[0, ch, cw]]
q = deque(q)
ans = -1
while q:
	(cnt, cx, cy) = q.popleft()
	if cost[cx][cy] < 0:
		cost[cx][cy] = cnt
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				if 0 <= cx + dx < h and 0 <= cy + dy < w and (s[cx + dx][cy + dy] == '.'):
					if cost[cx + dx][cy + dy] < 0:
						if [dx, dy] in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
							q.appendleft([cnt, cx + dx, cy + dy])
						else:
							q.append([cnt + 1, cx + dx, cy + dy])
print(cost[dh][dw])


(H, W) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
(sy, sx) = (sy - 1, sx - 1)
(gy, gx) = (gy - 1, gx - 1)
S = [input() for i in range(H)]
from collections import deque
INF = float('inf')
dist = [[INF] * W for _ in range(H)]
dist[sy][sx] = 0
q = deque([(sx, sy)])
while q:
	(x, y) = q.popleft()
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			if dx == dy == 0:
				continue
			(nx, ny) = (x + dx, y + dy)
			if not 0 <= nx < W:
				continue
			if not 0 <= ny < H:
				continue
			if S[ny][nx] == '#':
				continue
			if abs(dx) + abs(dy) <= 1:
				if dist[ny][nx] <= dist[y][x]:
					continue
				q.appendleft((nx, ny))
				dist[ny][nx] = dist[y][x]
			else:
				if dist[ny][nx] <= dist[y][x] + 1:
					continue
				q.append((nx, ny))
				dist[ny][nx] = dist[y][x] + 1
print(-1 if dist[gy][gx] == INF else dist[gy][gx])


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 = [input() for _ in range(h)]

def bfs(sx, sy):
	q = deque([(sx, sy)])
	d = [[10 ** 18] * w for _ in range(h)]
	d[sx][sy] = 0
	while q:
		(x, y) = q.popleft()
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				(nx, ny) = (x + dx, y + dy)
				if not (0 <= nx < h and 0 <= ny < w):
					continue
				if dx == 0 and dy == 0:
					continue
				if s[nx][ny] == '#':
					continue
				if abs(dx) + abs(dy) == 1:
					if d[nx][ny] > d[x][y]:
						d[nx][ny] = d[x][y]
						q.appendleft((nx, ny))
				elif d[nx][ny] > d[x][y] + 1:
					d[nx][ny] = d[x][y] + 1
					q.append((nx, ny))
	return d
d = bfs(ch, cw)
if d[dh][dw] == 10 ** 18:
	print(-1)
else:
	print(d[dh][dw])


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(H, W) = map(int, input().split())
(Ch, Cw) = map(lambda x: int(x) - 1, input().split())
(Dh, Dw) = map(lambda x: int(x) - 1, input().split())
S = [readline().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
	(d, i, j) = dq.popleft()
	if (i, j) == (Dh, Dw):
		print(d)
		exit()
	if visited[i][j]:
		continue
	visited[i][j] = True
	for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(ni, nj) = (i + di, j + dj)
		if 0 <= ni < H and 0 <= nj < W and (S[ni][nj] == '.'):
			dq.appendleft((d, ni, nj))
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if di == dj == 0:
				continue
			(ni, nj) = (i + di, j + dj)
			if 0 <= ni < H and 0 <= nj < W and (S[ni][nj] == '.') and (not visited[ni][nj]):
				dq.append((d + 1, ni, nj))
print(-1)


(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]
visited = [[-1] * W for i in range(H)]
visited[Ch - 1][Cw - 1] = 0
h = [(Ch - 1, Cw - 1)]
c = 0
while True:
	done = []
	while h:
		(cy, cx) = h.pop()
		done.append((cy, cx))
		visited[cy][cx] = c
		for (dy, dx) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
			(ny, nx) = (cy + dy, cx + dx)
			if 0 <= ny < H and 0 <= nx < W and (A[ny][nx] == '.') and (visited[ny][nx] == -1):
				h.append((ny, nx))
				visited[ny][nx] = c
	h = []
	for (cy, cx) in done:
		for dy in range(-2, 3):
			for dx in range(-2, 3):
				(ny, nx) = (cy + dy, cx + dx)
				if 0 <= ny < H and 0 <= nx < W and (A[ny][nx] == '.') and (visited[ny][nx] == -1):
					h.append((ny, nx))
	if not h:
		break
	c += 1
print(visited[Dh - 1][Dw - 1])


from collections import deque

def main():
	(H, W) = map(int, input().split())
	(Ch, Cw) = map(int, input().split())
	(Dh, Dw) = map(int, input().split())
	S = [list(input()) for _ in range(H)]
	d = [[-1 for _ in range(W)] for _ in range(H)]
	q = deque([])
	q.appendleft((0, Ch - 1, Cw - 1))
	while len(q):
		(worp_count, x, y) = q.popleft()
		if d[x][y] != -1:
			continue
		d[x][y] = worp_count
		for (i, j) in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
			nx = x + i
			ny = y + j
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == '.'):
				if i == 0 and j == 0:
					continue
				elif abs(i) + abs(j) == 1:
					q.appendleft((worp_count, nx, ny))
				else:
					q.append((worp_count + 1, nx, ny))
	print(d[Dh - 1][Dw - 1])
main()


(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 = ['#' * (W + 4)]
S.append('#' * (W + 4))
for k in range(H):
	S.append('##' + input() + '##')
S.append('#' * (W + 4))
S.append('#' * (W + 4))
foo = [[-1 for _ in range(W + 4)] for _ in range(H + 4)]
for k in range(2, H + 2):
	for j in range(2, W + 2):
		if S[k][j] == '.':
			foo[k][j] = 10 ** 6
foo[Ch][Cw] = 0
now = []
new = [(Ch, Cw)]
while len(new) > 0:
	item = new.pop()
	now.append(item)
	x = item[0]
	y = item[1]
	if foo[x + 1][y] == 10 ** 6:
		foo[x + 1][y] = 0
		new.append((x + 1, y))
	if foo[x][y + 1] == 10 ** 6:
		foo[x][y + 1] = 0
		new.append((x, y + 1))
	if foo[x - 1][y] == 10 ** 6:
		foo[x - 1][y] = 0
		new.append((x - 1, y))
	if foo[x][y - 1] == 10 ** 6:
		foo[x][y - 1] = 0
		new.append((x, y - 1))
ans = 0
while foo[Dh][Dw] == 10 ** 6:
	if len(now) == 0:
		print(-1)
		return
	ans += 1
	while len(now) > 0:
		item = now.pop()
		x = item[0]
		y = item[1]
		if foo[x + 2][y + 2] > ans:
			foo[x + 2][y + 2] = ans
			new.append((x + 2, y + 2))
		if foo[x + 2][y + 1] > ans:
			foo[x + 2][y + 1] = ans
			new.append((x + 2, y + 1))
		if foo[x + 2][y] > ans:
			foo[x + 2][y] = ans
			new.append((x + 2, y))
		if foo[x + 2][y - 1] > ans:
			foo[x + 2][y - 1] = ans
			new.append((x + 2, y - 1))
		if foo[x + 2][y - 2] > ans:
			foo[x + 2][y - 2] = ans
			new.append((x + 2, y - 2))
		if foo[x + 1][y + 2] > ans:
			foo[x + 1][y + 2] = ans
			new.append((x + 1, y + 2))
		if foo[x + 1][y - 2] > ans:
			foo[x + 1][y - 2] = ans
			new.append((x + 1, y - 2))
		if foo[x][y + 2] > ans:
			foo[x][y + 2] = ans
			new.append((x, y + 2))
		if foo[x][y - 2] > ans:
			foo[x][y - 2] = ans
			new.append((x, y - 2))
		if foo[x - 2][y + 2] > ans:
			foo[x - 2][y + 2] = ans
			new.append((x - 2, y + 2))
		if foo[x - 2][y + 1] > ans:
			foo[x - 2][y + 1] = ans
			new.append((x - 2, y + 1))
		if foo[x - 2][y] > ans:
			foo[x - 2][y] = ans
			new.append((x - 2, y))
		if foo[x - 2][y - 1] > ans:
			foo[x - 2][y - 1] = ans
			new.append((x - 2, y - 1))
		if foo[x - 2][y - 2] > ans:
			foo[x - 2][y - 2] = ans
			new.append((x - 2, y - 2))
		if foo[x - 1][y + 2] > ans:
			foo[x - 1][y + 2] = ans
			new.append((x - 1, y + 2))
		if foo[x - 1][y - 2] > ans:
			foo[x - 1][y - 2] = ans
			new.append((x - 1, y - 2))
		if foo[x - 1][y - 1] > ans:
			foo[x - 1][y - 1] = ans
			new.append((x - 1, y - 1))
		if foo[x - 1][y + 1] > ans:
			foo[x - 1][y + 1] = ans
			new.append((x - 1, y + 1))
		if foo[x + 1][y + 1] > ans:
			foo[x + 1][y + 1] = ans
			new.append((x + 1, y + 1))
		if foo[x + 1][y - 1] > ans:
			foo[x + 1][y - 1] = ans
			new.append((x + 1, y - 1))
	while len(new) > 0:
		item = new.pop()
		now.append(item)
		x = item[0]
		y = item[1]
		if foo[x + 1][y] == 10 ** 6:
			foo[x + 1][y] = 0
			new.append((x + 1, y))
		if foo[x][y + 1] == 10 ** 6:
			foo[x][y + 1] = 0
			new.append((x, y + 1))
		if foo[x - 1][y] == 10 ** 6:
			foo[x - 1][y] = 0
			new.append((x - 1, y))
		if foo[x][y - 1] == 10 ** 6:
			foo[x][y - 1] = 0
			new.append((x, y - 1))
print(ans)


(h, w) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
s = [list(input()) for _ in range(h)]
(Ch, Cw) = (Ch - 1, Cw - 1)
(Dh, Dw) = (Dh - 1, Dw - 1)
from collections import deque
todo = deque([[0, Ch, Cw]])
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
toho = [[0, 1], [0, -1], [1, 0], [-1, 0]]
wiz = [[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]]
while todo:
	(cnt, nh, nw) = todo.popleft()
	if d[nh][nw] < cnt:
		continue
	for (dh, dw) in toho:
		if 0 <= nh + dh < h and 0 <= nw + dw < w and (s[nh + dh][nw + dw] != '#'):
			if d[nh + dh][nw + dw] == -1 or d[nh + dh][nw + dw] > cnt:
				d[nh + dh][nw + dw] = cnt
				todo.appendleft([cnt, nh + dh, nw + dw])
	for (dh, dw) in wiz:
		if 0 <= nh + dh < h and 0 <= nw + dw < w and (s[nh + dh][nw + dw] != '#'):
			if d[nh + dh][nw + dw] == -1 or d[nh + dh][nw + dw] > cnt + 1:
				d[nh + dh][nw + dw] = cnt + 1
				todo.append([cnt + 1, nh + dh, nw + dw])
print(d[Dh][Dw])


f = lambda : map(int, input().split())
(h, w) = f()
(ch, cw) = f()
(dh, dw) = f()
g = [[*input()] for _ in range(h)]
from collections import *
q = deque([(0, ch - 1, cw - 1)])
while q:
	(d, x, y) = q.popleft()
	if g[x][y] != '.':
		continue
	g[x][y] = d
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			j = abs(dx) + abs(dy)
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and j:
				if j > 1:
					q.append((d + 1, nx, ny))
				else:
					q.appendleft((d, nx, ny))
a = g[dh - 1][dw - 1]
print([a, -1][a == '.'])


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(lambda x: int(x) - 1, input().split())
(dh, dw) = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(h)]
INF = 10 ** 12
path = [[INF] * w for _ in range(h)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
q = deque()
path[ch][cw] = 0
q.append((ch, cw, 0))
while q:
	(x, y, s) = q.popleft()
	for (dx, dy) in walk:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] != '#') and (path[nx][ny] > s):
			path[nx][ny] = s
			q.appendleft((nx, ny, s))
	for (dx, dy) in warp:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] != '#') and (path[nx][ny] > s + 1):
			path[nx][ny] = s + 1
			q.append((nx, ny, s + 1))
ans = path[dh][dw] if path[dh][dw] < INF else -1
print(ans)


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
S = [input() for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[ch - 1][cw - 1] = 0
h = deque([(ch - 1, cw - 1)])
c = 0
while 1:
	done = []
	while h:
		(cx, cy) = h.popleft()
		done.append((cx, cy))
		for (dx, dy) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			(nx, ny) = (cx + dx, cy + dy)
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == '.') and (visited[nx][ny] == -1):
				h.append((nx, ny))
				visited[nx][ny] = c
	for (cx, cy) in done:
		for dx in range(-2, 3):
			for dy in range(-2, 3):
				(nx, ny) = (cx + dx, cy + dy)
				if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == '.') and (visited[nx][ny] == -1):
					h.append((nx, ny))
					visited[nx][ny] = c + 1
	if not h or visited[dh - 1][dw - 1] != -1:
		break
	c += 1
print(visited[dh - 1][dw - 1])


from collections import deque
from itertools import product
(h, w) = list(map(int, input().split()))
(sy, sx) = list(map(int, input().split()))
(gy, gx) = list(map(int, input().split()))
(sx, sy, gx, gy) = (sx - 1, sy - 1, gx - 1, gy - 1)
G = [list(input()) for _ in range(h)]
D = [[10 ** 6] * w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
	(y, x) = Q.pop()
	for (dy, dx) in product(range(-2, 3), repeat=2):
		(ny, nx) = (y + dy, x + dx)
		if dx == dy == 0:
			G[y][x] = '#'
		elif (0 <= ny < h and 0 <= nx < w) and G[ny][nx] != '#':
			if abs(dy) + abs(dx) <= 1:
				G[ny][nx] = '#'
				D[ny][nx] = D[y][x]
				Q.append((ny, nx))
			elif D[ny][nx] == 10 ** 6:
				D[ny][nx] = D[y][x] + 1
				Q.appendleft((ny, nx))
if D[gy][gx] == 10 ** 6:
	print(-1)
else:
	print(D[gy][gx])


import sys
input = lambda : sys.stdin.readline().rstrip()
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
ch -= 1
cw -= 1
stack = [(ch, cw)]
(dh, dw) = map(int, input().split())
dh -= 1
dw -= 1
b = [w * [-1] for _ in range(h)]
for i in range(h):
	for (j, t) in enumerate(input()):
		if t == '#':
			b[i][j] = 10 ** 10
b[ch][cw] = 0
dxy = ((-1, 0), (1, 0), (0, -1), (0, 1))
for ans in range(10 ** 6):
	for (x, y) in stack:
		b[x][y] = 1
		if x == dh and y == dw:
			print(ans)
			exit()
		for (dx, dy) in dxy:
			if 0 <= x + dx < h and 0 <= y + dy < w:
				if b[x + dx][y + dy] == 10 ** 10:
					continue
				if b[x + dx][y + dy] == -1:
					stack.append((x + dx, y + dy))
					b[x + dx][y + dy] = 1
	stackk = []
	for (x, y) in stack:
		for xx in range(max(0, x - 2), min(h, x + 3)):
			for yy in range(max(0, y - 2), min(w, y + 3)):
				if b[xx][yy] == -1:
					stackk.append((xx, yy))
	stack = stackk
print(-1)


(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
S = [input() for i in range(H)]
from collections import deque
q = deque([(ch - 1, cw - 1, 0)])
v = [[9 ** 9] * W for i in range(H)]
x = ((1, 0), (-1, 0), (0, -1), (0, 1))
y = ((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))
while q:
	(h, w, d) = q.popleft()
	for (i, j) in x:
		if 0 <= h + i < H and 0 <= w + j < W and (S[h + i][w + j] == '.') and (d < v[h + i][w + j]):
			v[h + i][w + j] = d
			q.appendleft((h + i, w + j, d))
	for (i, j) in y:
		if 0 <= h + i < H and 0 <= w + j < W and (S[h + i][w + j] == '.') and (d + 1 < v[h + i][w + j]):
			v[h + i][w + j] = d + 1
			q.append((h + i, w + j, d + 1))
print(v[dh - 1][dw - 1] if v[dh - 1][dw - 1] < 9 ** 9 else -1)


from collections import deque
(H, W) = map(int, input().split())
(c1, c2) = map(int, input().split())
(d1, d2) = map(int, input().split())
c1 += 1
c2 += 1
d1 += 1
d2 += 1
S = ['#' * (W + 4)] * 2 + ['##' + input() + '##' for _ in range(H)] + ['#' * (W + 4)] * 2
ans = [[10000000] * (W + 4) for _ in range(H + 4)]
ans[c1][c2] = 0
q = deque([[c1, c2]])
x = [[-1, 0], [0, -1], [0, 1], [1, 0]]
while q:
	(h, w) = q.popleft()
	for (a, b) in x:
		nh = h + a
		nw = w + b
		if S[nh][nw] == '.':
			if ans[nh][nw] > ans[h][w]:
				ans[nh][nw] = ans[h][w]
				q.appendleft([nh, nw])
	for a in range(-2, 3):
		for b in range(-2, 3):
			nh = h + a
			nw = w + b
			if S[nh][nw] == '.':
				if ans[nh][nw] > ans[h][w] + 1:
					ans[nh][nw] = ans[h][w] + 1
					q.append([nh, nw])
if ans[d1][d2] == 10000000:
	print(-1)
else:
	print(ans[d1][d2])


(H, W) = map(int, input().split())
(sh, sw) = map(int, input().split())
(gh, gw) = map(int, input().split())
sh += 1
sw += 1
gh += 1
gw += 1
S = [0] * (H + 4)
S[0] = '*' * (W + 4)
S[1] = '*' * (W + 4)
S[-2] = '*' * (W + 4)
S[-1] = '*' * (W + 4)
for h in range(2, H + 2):
	S[h] = '**' + input() + '**'
visited = [[float('inf')] * (W + 4) for _ in range(H + 4)]
dh1 = [0, 1, 0, -1]
dw1 = [1, 0, -1, 0]
dh2 = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
dw2 = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
from collections import deque
d = deque()
d.append((sh, sw, 0))
while len(d) > 0:
	(h, w, cnt) = d.popleft()
	if visited[h][w] <= cnt:
		continue
	visited[h][w] = cnt
	for i in range(4):
		h1 = h + dh1[i]
		w1 = w + dw1[i]
		if S[h1][w1] == '.':
			if visited[h1][w1] > cnt:
				d.appendleft((h1, w1, cnt))
	for i in range(20):
		h2 = h + dh2[i]
		w2 = w + dw2[i]
		if S[h2][w2] == '.':
			if visited[h2][w2] > cnt + 1:
				d.append((h2, w2, cnt + 1))
ans = visited[gh][gw] if visited[gh][gw] < float('inf') else -1
print(ans)


(h, w) = map(int, input().split())
(sy, sx) = map(int, input().split())
(gy, gx) = map(int, input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
s = [input() for i in range(h)]
from collections import deque
q = deque([])
q.append([sy, sx, 0])
mx = [0, 0, 1, -1]
my = [1, -1, 0, 0]
vis = [[-1] * w for i in range(h)]
vis[sy][sx] = 0
while len(q) > 0:
	(y, x, c) = q.popleft()
	for i in range(4):
		nx = x + mx[i]
		ny = y + my[i]
		if 0 <= nx < w and 0 <= ny < h and (s[ny][nx] == '.') and (vis[ny][nx] > c or vis[ny][nx] == -1):
			vis[ny][nx] = c
			q.appendleft([ny, nx, c])
	for xi in range(5):
		for yi in range(5):
			nx = x + xi - 2
			ny = y + yi - 2
			if 0 <= nx < w and 0 <= ny < h and (s[ny][nx] == '.') and (vis[ny][nx] == -1):
				vis[ny][nx] = c + 1
				q.append([ny, nx, c + 1])
print(vis[gy][gx])


(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)]
cnt = [[-1] * w for _ in range(h)]
cnt[ch][cw] = 0
from collections import deque
q = deque()
q2 = deque()
q.append((ch, cw))
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
d2 = [(i - 2, j - 2) for i in range(5) for j in range(5)]
tmp = 0
while q2 or q:
	while q:
		(y, x) = q.popleft()
		q2.append((y, x))
		for (dx, dy) in d:
			if 0 <= y + dy <= h - 1 and 0 <= x + dx <= w - 1 and (s[y + dy][x + dx] == '.') and (cnt[y + dy][x + dx] < 0):
				cnt[y + dy][x + dx] = cnt[y][x]
				q.append((y + dy, x + dx))
	(y, x) = q2.popleft()
	tmp += 1
	for (dx, dy) in d2:
		if 0 <= y + dy <= h - 1 and 0 <= x + dx <= w - 1 and (s[y + dy][x + dx] == '.') and (cnt[y + dy][x + dx] < 0):
			cnt[y + dy][x + dx] = cnt[y][x] + 1
			q.append((y + dy, x + dx))
print(cnt[dh][dw])


from collections import deque
(H, W) = map(int, input().split())
C_pos = list(map(lambda x: int(x) - 1, input().split()))
D_pos = list(map(lambda x: int(x) - 1, input().split()))
Grid = [[c for c in input()] for _ in range(H)]
Dist = [[float('inf')] * W for _ in range(H)]
DX = [0, 0, 1, -1]
Q = deque()
Q.append((C_pos[0], C_pos[1]))
Dist[C_pos[0]][C_pos[1]] = 0
while Q:
	(cx, cy) = Q.pop()
	for (dx, dy) in zip(DX, reversed(DX)):
		nx = cx + dx
		ny = cy + dy
		if 0 <= nx < H and 0 <= ny < W and (Grid[nx][ny] == '.') and (Dist[nx][ny] > Dist[cx][cy]):
			Dist[nx][ny] = Dist[cx][cy]
			Q.append((nx, ny))
	for dx in range(-2, 3):
		for dy in range(-2, 3):
			nx = cx + dx
			ny = cy + dy
			if dx == 0 and dy == 0:
				continue
			if 0 <= nx < H and 0 <= ny < W and (Grid[nx][ny] == '.') and (Dist[nx][ny] == float('inf')):
				Dist[nx][ny] = Dist[cx][cy] + 1
				Q.appendleft((nx, ny))
ans = Dist[D_pos[0]][D_pos[1]]
if ans == float('inf'):
	print(-1)
else:
	print(ans)


import collections
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [input() for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
d = collections.deque()
d.append((ch, cw))
visit = set()
x = ch
y = cw
cost = [[-1] * w for _ in range(h)]
cost[ch][cw] = 0
while len(d) > 0:
	(x, y) = d.popleft()
	if (x, y) not in visit:
		visit.add((x, y))
	else:
		continue
	for i in range(5):
		for j in range(5):
			x_n = x + i - 2
			y_n = y + j - 2
			if x_n >= 0 and x_n < h and (y_n >= 0) and (y_n < w):
				if s[x_n][y_n] == '.' and (x_n, y_n) not in visit:
					if pow(i - 2, 2) + pow(j - 2, 2) == 1:
						d.appendleft((x_n, y_n))
						cost[x_n][y_n] = cost[x][y]
					else:
						d.append((x_n, y_n))
						if cost[x_n][y_n] == -1:
							cost[x_n][y_n] = cost[x][y] + 1
print(cost[dh][dw])


from collections import deque
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
magic = [[i, j] for i in range(-2, 3) for j in range(-2, 3)]
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Ch, Cw) = (Ch - 1, Cw - 1)
(Dh, Dw) = map(int, input().split())
(Dh, Dw) = (Dh - 1, Dw - 1)
S = [list(input()) for i in range(H)]
is_visited = [[-1 for j in range(W)] for i in range(H)]
d = deque()
d.appendleft((0, (Ch, Cw)))
while d:
	(cost, (x, y)) = d.popleft()
	if is_visited[x][y] != -1:
		continue
	is_visited[x][y] = cost
	for (dx, dy) in lrud:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < H and 0 <= ny < W and (is_visited[nx][ny] == -1) and (S[nx][ny] == '.'):
			d.appendleft((cost, (nx, ny)))
	for (dx, dy) in magic:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < H and 0 <= ny < W and (is_visited[nx][ny] == -1) and (S[nx][ny] == '.'):
			d.append((cost + 1, (nx, ny)))
print(is_visited[Dh][Dw])


from collections import deque
(H, W) = map(int, input().split())
(Ch, Cw) = map(int, input().split())
(Dh, Dw) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
warp = [[-1 for i in range(W)] for j in range(H)]
Q = deque([[Ch - 1, Cw - 1, 0]])
while len(Q) != 0:
	(x, y, cnt) = Q.popleft()
	if warp[x][y] != -1:
		continue
	warp[x][y] = cnt
	for tx in range(-2, 3):
		for ty in range(-2, 3):
			nx = x + tx
			ny = y + ty
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == '.'):
				if abs(tx) + abs(ty) == 1:
					Q.appendleft([nx, ny, cnt])
				elif abs(tx) + abs(ty) >= 2:
					Q.append([nx, ny, cnt + 1])
print(warp[Dh - 1][Dw - 1])


from collections import deque
(H, W) = map(int, input().split())
(sh, sw) = map(int, input().split())
(gh, gw) = map(int, input().split())
(sh, sw, gh, gw) = (sh - 1, sw - 1, gh - 1, gw - 1)
S = [input() for _ in range(H)]
INF = 10 ** 9
ans = [[INF] * W for _ in range(H)]
ans[sh][sw] = 0
Q = deque([[sh, sw]])
while Q:
	(h, w) = Q.popleft()
	for (nh, nw) in [[h, w + 1], [h, w - 1], [h + 1, w], [h - 1, w]]:
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (ans[nh][nw] > ans[h][w]):
			ans[nh][nw] = ans[h][w]
			Q.appendleft([nh, nw])
	for nh in range(h - 2, h + 3):
		for nw in range(w - 2, w + 3):
			if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (ans[nh][nw] > ans[h][w] + 1):
				ans[nh][nw] = ans[h][w] + 1
				Q.append([nh, nw])
if ans[gh][gw] == INF:
	print(-1)
else:
	print(ans[gh][gw])


def check(g, h, w, s):
	if (g[0] < 0 or g[0] >= h) or (g[1] < 0 or g[1] >= w):
		return False
	if s[g[0]][g[1]] == -1:
		return True
	else:
		return False
(h, w) = map(int, input().split())
c = [int(x) - 1 for x in input().split()]
d = [int(x) - 1 for x in input().split()]
s = []
for j in range(h):
	l = [-1 if x == '.' else -2 for x in list(input())]
	s.append(l)
s[c[0]][c[1]] = 0
u = [c]
i = 0
t = 0
while t == 0:
	for j in u:
		if j == d:
			t = 1
			break
		for k in [[j[0] - 1, j[1]], [j[0] + 1, j[1]], [j[0], j[1] - 1], [j[0], j[1] + 1]]:
			if check(k, h, w, s):
				s[k[0]][k[1]] = i
				u.append(k)
	i += 1
	v = []
	for j in u:
		if j == d:
			t = 1
			break
		for k1 in range(-2, 3):
			for k2 in range(-2, 3):
				k = [j[0] + k1, j[1] + k2]
				if check(k, h, w, s):
					s[k[0]][k[1]] = i
					v.append(k)
	if v == []:
		t = 1
	u = v
print(s[d[0]][d[1]])


from collections import deque
from sys import exit
(h, w) = map(int, input().split())
(sh, sw) = map(lambda s: int(s) - 1, input().split())
(gh, gw) = map(lambda s: int(s) - 1, input().split())
s = [input() for _ in range(h)]
d = [[h * w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh, 0))
while len(q):
	p = q.popleft()
	if p[2] != d[p[1]][p[0]]:
		continue
	if p[0] == gw and p[1] == gh:
		print(d[gh][gw])
		exit(0)
	for dx in range(-2, 3):
		nx = p[0] + dx
		if nx < 0 or w <= nx:
			continue
		for dy in range(-2, 3):
			ny = p[1] + dy
			c = 0 if abs(dx) + abs(dy) == 1 else 1
			if dx == dy == 0 or ny < 0 or h <= ny or (s[ny][nx] == '#') or (d[ny][nx] <= d[p[1]][p[0]] + c):
				continue
			d[ny][nx] = d[p[1]][p[0]] + c
			np = (nx, ny, d[ny][nx])
			if c:
				q.append(np)
			else:
				q.appendleft(np)
print(-1)


(h, w) = map(int, input().split())
from collections import *
l = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dp = [[float('inf')] * w for i in range(h)]
f = [[False] * w for i in range(h)]
(ch, cw) = map(int, input().split())
(sx, sy) = (ch - 1, cw - 1)
(dh, dw) = map(int, input().split())
(gx, gy) = (dh - 1, dw - 1)
for i in range(h):
	s = input()
	for j in range(w):
		if s[j] == '.':
			f[i][j] = True
q = deque()
q.append((sx, sy))
dp[sx][sy] = 0
while q:
	(x, y) = q.popleft()
	for (a, b) in l:
		(nx, ny) = (x + a, y + b)
		if 0 <= nx < h and 0 <= ny < w:
			if f[nx][ny] == True and dp[nx][ny] > dp[x][y]:
				dp[nx][ny] = dp[x][y]
				q.appendleft((nx, ny))
	for nx in range(x - 2, x + 3):
		for ny in range(y - 2, y + 3):
			if 0 <= nx < h and 0 <= ny < w:
				if f[nx][ny] == True and dp[nx][ny] > dp[x][y] + 1:
					dp[nx][ny] = dp[x][y] + 1
					q.append((nx, ny))
if dp[gx][gy] == float('inf'):
	print(-1)
else:
	print(dp[gx][gy])


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
C = (Ch, Cw)
D = (Dh, Dw)
S = [list(input()) for i in range(H)]
dist = [[10 ** 15 for j in range(W)] for i in range(H)]
dist[Ch][Cw] = 0
q = deque([C])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while len(q) > 0:
	(x, y) = q.popleft()
	for k in range(4):
		nx = x + dx[k]
		ny = y + dy[k]
		if 0 <= nx < H and 0 <= ny < W:
			if S[nx][ny] == '#':
				continue
			if dist[nx][ny] > dist[x][y]:
				dist[nx][ny] = dist[x][y]
				q.appendleft((nx, ny))
	for i in range(-2, 3):
		for j in range(-2, 3):
			nx = x + i
			ny = y + j
			if 0 <= nx < H and 0 <= ny < W:
				if S[nx][ny] == '#':
					continue
				if dist[nx][ny] > dist[x][y] + 1:
					dist[nx][ny] = dist[x][y] + 1
					q.append((nx, ny))
if dist[Dh][Dw] == 10 ** 15:
	print(-1)
else:
	print(dist[Dh][Dw])


import heapq
import numpy as np
from numba import njit, i8, b1
(h, w) = map(int, input().split())
(sh, sw) = map(int, input().split())
(gh, gw) = map(int, input().split())
s = np.array([list(input()) for _ in range(h)]) == '#'

@njit(i8(i8, i8, i8, i8, i8, i8, b1[:, :]))
def solve(h, w, sh, sw, gh, gw, s):
	sh -= 1
	sw -= 1
	gh -= 1
	gw -= 1
	INF = 10 ** 7
	dist = [[INF] * w for _ in range(h)]
	dist[sh][sw] = 0
	q = [(0, sh, sw)]
	while q:
		(d, vsh, vsw) = heapq.heappop(q)
		for dh in range(-2, 3):
			for dw in range(-2, 3):
				newh = vsh + dh
				neww = vsw + dw
				if newh < 0 or h <= newh or neww < 0 or (w <= neww):
					continue
				if dh == 0 and dw == 0:
					continue
				if s[newh][neww]:
					continue
				if abs(dh) + abs(dw) == 1:
					if dist[newh][neww] > d:
						dist[newh][neww] = d
						if newh == gh and neww == gw:
							return d
						heapq.heappush(q, (d, newh, neww))
				elif dist[newh][neww] > d + 1:
					dist[newh][neww] = d + 1
					heapq.heappush(q, (d + 1, newh, neww))
	if dist[gh][gw] == INF:
		return -1
	else:
		return dist[gh][gw]
print(solve(h, w, sh, sw, gh, gw, s))


dhw = [(1, 0), (0, -1), (0, 1), (-1, 0), (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)]
(H, W) = map(int, input().split())
(sh, sw) = map(lambda x: int(x) - 1, input().split())
(eh, ew) = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]
dst = [[-1] * W for _ in range(H)]
from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
	(h, w, d) = dq.popleft()
	if h < 0 or H <= h or w < 0 or (W <= w) or (dst[h][w] >= 0) or (S[h][w] == '#'):
		continue
	dst[h][w] = d
	for i in range(4):
		dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
	for i in range(4, 24):
		dq.append((h + dhw[i][0], w + dhw[i][1], d + 1))
print(dst[eh][ew])


from collections import deque
(H, W) = map(int, input().split())
(C_1, C_2) = map(int, input().split())
(D_1, D_2) = map(int, input().split())
T = []
for i in range(H):
	A = list(input())
	T.append(A)
used = [[0] * W for _ in range(H)]
P = deque([(C_1 - 1, C_2 - 1, 0)])
while True:
	if len(P) == 0:
		print(-1)
		break
	(a, b, cost) = P.popleft()
	if (a, b) == (D_1 - 1, D_2 - 1):
		print(cost)
		break
	if used[a][b] == 0:
		used[a][b] = 1
		for (i, j) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
			if 0 <= a + i <= H - 1:
				if 0 <= b + j <= W - 1:
					if T[a + i][b + j] == '.':
						P.appendleft((a + i, b + j, cost))
		for i in range(-2, 3):
			for j in range(-2, 3):
				if 0 <= a + i <= H - 1:
					if 0 <= b + j <= W - 1:
						if T[a + i][b + j] == '.':
							P.append((a + i, b + j, cost + 1))


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(gh, gw) = map(int, input().split())
s = [input() for _ in range(H)]
res = [[10 ** 8 for _ in range(W)] for _ in range(H)]
res[ch - 1][cw - 1] = 0
deq = deque([(ch - 1, cw - 1)])
DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

def inc(h, w):
	if 0 <= h < H and 0 <= w < W:
		return True
	else:
		return False
while deq:
	(h, w) = deq.pop()
	for (dh, dw) in zip(DH, DW):
		if inc(h + dh, w + dw) == False or s[h + dh][w + dw] == '#':
			continue
		if res[h + dh][w + dw] > res[h][w]:
			res[h + dh][w + dw] = res[h][w]
			deq.append((h + dh, w + dw))
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			if inc(h + dh, w + dw) == False or s[h + dh][w + dw] == '#':
				continue
			if res[h + dh][w + dw] > res[h][w] + 1:
				res[h + dh][w + dw] = res[h][w] + 1
				deq.appendleft((h + dh, w + dw))
if res[gh - 1][gw - 1] > 10 ** 7:
	print(-1)
else:
	print(res[gh - 1][gw - 1])


from collections import deque
(H, W) = map(int, input().split())
(C_h, C_w) = map(lambda x: int(x) - 1, input().split())
(D_h, D_w) = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]
INF = int(10000000000.0)
dist = [[INF] * W for _ in range(H)]
deq = deque()
deq.append((C_h, C_w, 0))
move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(i, j) for i in range(-2, 2 + 1) for j in range(-2, 2 + 1) if abs(i) + abs(j) >= 2]
while len(deq):
	(h, w, c) = deq.popleft()
	if dist[h][w] <= c:
		continue
	dist[h][w] = c
	for (dh, dw) in move_a:
		(nh, nw) = (h + dh, w + dw)
		if nh < 0 or nw < 0 or nh >= H or (nw >= W):
			continue
		if S[nh][nw] == '#':
			continue
		if dist[nh][nw] > c:
			deq.appendleft((nh, nw, c))
	for (dh, dw) in move_b:
		(nh, nw) = (h + dh, w + dw)
		if nh < 0 or nw < 0 or nh >= H or (nw >= W):
			continue
		if S[nh][nw] == '#':
			continue
		if dist[nh][nw] > c + 1:
			deq.append((nh, nw, c + 1))
print(dist[D_h][D_w] if dist[D_h][D_w] < INF else -1)


from collections import deque

def solve(H, W, Ch, Cw, Dh, Dw, maze):
	walled_maze = ['##{}##'.format(row) for row in maze]
	walled_maze.insert(0, '##{}##'.format('#' * W))
	walled_maze.insert(0, '##{}##'.format('#' * W))
	walled_maze.append('##{}##'.format('#' * W))
	walled_maze.append('##{}##'.format('#' * W))
	INF = 10 ** 12
	path = [[INF] * (W + 4) for _ in range(H + 4)]
	walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
	warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
	yet = deque()
	yet.append((Ch + 2, Cw + 2, 0))
	path[Ch + 2][Cw + 2] = 0
	done = deque()
	while yet:
		(y, x, s) = yet.popleft()
		done.append((y, x, s))
		for (dy, dx) in walk:
			ny = y + dy
			nx = x + dx
			if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
				path[ny][nx] = s
				yet.append((ny, nx, s))
		if len(yet) == 0:
			while done:
				(y, x, s) = done.popleft()
				for (dy, dx) in warp:
					ny = y + dy
					nx = x + dx
					if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
						path[ny][nx] = s + 1
						yet.append((ny, nx, s + 1))
	ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
	print(ans)

def __starting_point():
	(H, W) = list(map(int, input().split()))
	(Ch, Cw) = [int(x) - 1 for x in input().split()]
	(Dh, Dw) = [int(x) - 1 for x in input().split()]
	maze = [input() for _ in range(H)]
	solve(H, W, Ch, Cw, Dh, Dw, maze)
__starting_point()


from collections import deque
from itertools import product
(H, W) = map(int, input().split())
C = tuple(map(lambda x: int(x) - 1, input().split()))
D = tuple(map(lambda x: int(x) - 1, input().split()))
S = [input().strip('¥n') for i in range(H)]
mag = (-2, -1, 0, 1, 2)
dist = [[-1] * W for i in range(H)]
qu = deque([(C[0], C[1])])
dist[C[0]][C[1]] = 0
while len(qu) > 0:
	qut = deque()
	while len(qu) > 0:
		v = qu.popleft()
		qut.append(v)
		for (h, w) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			nvh = v[0] + h
			nvw = v[1] + w
			if 0 <= nvh < H and 0 <= nvw < W and (dist[nvh][nvw] == -1) and (S[nvh][nvw] == '.'):
				dist[nvh][nvw] = dist[v[0]][v[1]]
				qu.append((nvh, nvw))
	while len(qut) > 0:
		v = qut.popleft()
		for (h, w) in product(mag, repeat=2):
			if h == 0 and w == 0:
				continue
			nvh = v[0] + h
			nvw = v[1] + w
			if 0 <= nvh < H and 0 <= nvw < W and (S[nvh][nvw] == '.'):
				if dist[nvh][nvw] == -1:
					dist[nvh][nvw] = dist[v[0]][v[1]] + 1
					qu.append((nvh, nvw))
print(dist[D[0]][D[1]])


from collections import deque

def bfs():
	(H, W) = map(int, input().split())
	(sy, sx) = map(int, input().split())
	(gy, gx) = map(int, input().split())
	S = ['#' * (W + 4), '#' * (W + 4)]
	for _ in range(H):
		S.append('##' + input() + '##')
	S.append('#' * (W + 4))
	S.append('#' * (W + 4))
	dist = [[-2] * (W + 4) for _ in range(H + 4)]
	for i in range(H + 4):
		for j in range(W + 4):
			if S[i][j] == '.':
				dist[i][j] = -1
	dist[sy + 1][sx + 1] = 0
	A = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	B = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i) + abs(j) > 1]
	que = deque([[sx + 1, sy + 1]])
	que2 = deque([])
	while que:
		(x, y) = que.popleft()
		que2.appendleft([x, y])
		for (dx, dy) in A:
			nx = x + dx
			ny = y + dy
			if dist[ny][nx] == -1:
				dist[ny][nx] = dist[y][x]
				que.appendleft([nx, ny])
		if que:
			continue
		while que2:
			(x, y) = que2.popleft()
			for (dx, dy) in B:
				nx = x + dx
				ny = y + dy
				if dist[ny][nx] == -1:
					dist[ny][nx] = dist[y][x] + 1
					que.append([nx, ny])
	ans = dist[gy + 1][gx + 1]
	return ans
print(bfs())


from heapq import heapify, heappop, heappush
inpl = lambda : list(map(int, input().split()))
(H, W) = inpl()
(sh, sw) = inpl()
start = (sh - 1, sw - 1)
(gh, gw) = inpl()
goal = (gh - 1, gw - 1)
S = [input() for _ in range(H)]
count = [[-1] * W for _ in range(H)]
count[start[0]][start[1]] = 0
q = [(0, start)]
while q:
	(d, p) = heappop(q)
	if p == goal:
		print(d)
		exit()
	(h, w) = p
	if d > count[h][w]:
		continue
	for (dh, dw) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		(nh, nw) = (h + dh, w + dw)
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (count[nh][nw] < 0 or count[nh][nw] > d):
			count[nh][nw] = d
			heappush(q, (d, (nh, nw)))
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			(nh, nw) = (h + dh, w + dw)
			if (dh, dw) != (0, 0) and 0 <= nh < H and (0 <= nw < W) and (S[nh][nw] == '.') and (count[nh][nw] < 0):
				count[nh][nw] = d + 1
				heappush(q, (d + 1, (nh, nw)))
print(-1)


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
maze = [list(input()) for i in range(h)]
Q = deque()
Q.append((ch, cw, 0))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [2, 2, 2, 2, 2, -2, -2, -2, -2, -2, 1, 1, 1, 1, -1, -1, -1, -1, 0, 0]
ddy = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, 2, 1, -1, -2, 2, 1, -1, -2, 2, -2]
dp = [[float('inf')] * w for i in range(h)]
while Q:
	p = Q.popleft()
	if p[0] == dh and p[1] == dw:
		print(p[2])
		exit()
	for i in range(4):
		nx = p[0] + dx[i]
		ny = p[1] + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] == '.') and (p[2] < dp[nx][ny]):
			Q.appendleft((nx, ny, p[2]))
			dp[nx][ny] = p[2]
	for j in range(20):
		nnx = p[0] + ddx[j]
		nny = p[1] + ddy[j]
		if 0 <= nnx < h and 0 <= nny < w and (maze[nnx][nny] == '.') and (p[2] + 1 < dp[nnx][nny]):
			Q.append((nnx, nny, p[2] + 1))
			dp[nnx][nny] = p[2] + 1
print(-1)


from collections import deque
(h, w) = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = []
for i in range(h):
	s += [input()]
t = [[h * w] * w for i in range(h)]
t[c[0] - 1][c[1] - 1] = 0
p = deque([[c[0] - 1, c[1] - 1]])
while p:
	q = p.popleft()
	u = t[q[0]][q[1]]
	for i in range(-2, 3):
		if 0 <= q[0] + i and q[0] + i < h:
			for j in range(-2, 3):
				if 0 <= q[1] + j and q[1] + j < w:
					if s[q[0] + i][q[1] + j] == '.':
						if abs(i) + abs(j) == 1:
							if t[q[0] + i][q[1] + j] > u:
								t[q[0] + i][q[1] + j] = u
								p.appendleft([q[0] + i, q[1] + j])
						elif t[q[0] + i][q[1] + j] > u + 1:
							t[q[0] + i][q[1] + j] = u + 1
							p.append([q[0] + i, q[1] + j])
ans = t[d[0] - 1][d[1] - 1]
if ans == h * w:
	ans = -1
print(ans)


from collections import deque
(H, W) = map(int, input().split())
(Ch, Cw) = map(lambda x: int(x) - 1, input().split())
(Dh, Dw) = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
INF = 10 ** 12
path = [[INF] * W for _ in range(H)]
q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
while q:
	(x, y, s) = q.popleft()
	for (dx, dy) in walk:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and (maze[nx][ny] == '.') and (path[nx][ny] > s):
			path[nx][ny] = s
			q.appendleft((nx, ny, s))
	for (dx, dy) in warp:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and (maze[nx][ny] == '.') and (path[nx][ny] > s + 1):
			path[nx][ny] = s + 1
			q.append((nx, ny, s + 1))
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)


from collections import deque
(H, W) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh_, dw_) = map(int, input().split())
fs = [input() for i in range(H)]
INF = float('inf')
N = 10 ** 4
dps = [[INF] * W for i in range(H)]
dps[ch - 1][cw - 1] = 0
q = deque([])
q.append((0, (ch - 1) * N + (cw - 1)))
while q:
	(cnt, n) = q.popleft()
	(h, w) = divmod(n, N)
	if cnt > dps[h][w]:
		continue
	dps[h][w] = cnt
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			hn = h + dh
			wn = w + dw
			if not 0 <= wn < W:
				continue
			if not 0 <= hn < H:
				continue
			if fs[hn][wn] == '#':
				continue
			if dps[hn][wn] < INF:
				continue
			if abs(dh) + abs(dw) <= 1:
				q.appendleft((cnt, hn * N + wn))
			else:
				q.append((cnt + 1, hn * N + wn))
ans = dps[dh_ - 1][dw_ - 1]
print(ans if ans != INF else -1)


from collections import deque
int1 = lambda x: int(x) - 1
(H, W) = map(int, input().split())
(Ch, Cw) = map(int1, input().split())
(Dh, Dw) = map(int1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(H)]
d = deque([(Ch, Cw)])
cur = 1
while True:
	visited = set()
	while d:
		(h, w) = d.pop()
		visited.add((h, w))
		S[h][w] = cur
		if (h, w) == (Dh, Dw):
			print(cur - 1)
			exit()
		for (dh, dw) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			if 0 <= h + dh < H and 0 <= w + dw < W and (S[h + dh][w + dw] == 0):
				d.append((h + dh, w + dw))
	for (h, w) in visited:
		for dh in range(-2, 3):
			for dw in range(-2, 3):
				if 0 <= h + dh < H and 0 <= w + dw < W and (S[h + dh][w + dw] == 0):
					d.append((h + dh, w + dw))
	if not d:
		print(-1)
		exit()
	cur += 1


from collections import deque
(H, W) = map(int, input().split())
(cy, cx) = map(int, input().split())
(dy, dx) = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]
worps = [[float('inf')] * W for _ in range(H)]
q = deque([[cy, cx]])
worps[cy][cx] = 0
while q:
	(y, x) = q.popleft()
	worp = worps[y][x]
	for (h, w) in d:
		(ny, nx) = (y + h, x + w)
		if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == '.') and (worp < worps[ny][nx]):
			worps[ny][nx] = worp
			q.appendleft([ny, nx])
	worp += 1
	for h in range(-2 + y, 3 + y):
		for w in range(-2 + x, 3 + x):
			if 0 <= h < H and 0 <= w < W and (S[h][w] == '.') and (worp < worps[h][w]):
				worps[h][w] = worp
				q.append([h, w])
ans = worps[dy][dx]
if ans != float('inf'):
	print(ans)
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
(ch, cw) = map(int, input().split())
(dh, dw) = map(int, input().split())
s = [input() for _ in range(h)]
vi = [[-1 for _ in range(w)] for _ in range(h)]
st = deque()
st2 = deque()
st.append([ch - 1, cw - 1])
vi[ch - 1][cw - 1] = 1
c = 0
d = [[0, 1], [-1, 0], [1, 0], [0, -1]]
d2 = [[-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]]
while st or st2:
	while st:
		s2 = 0
		(h1, w1) = st.popleft()
		if dh - 1 == h1 and dw - 1 == w1:
			print(c)
			exit()
		for m in d:
			x = w1 + m[1]
			y = h1 + m[0]
			if 0 <= y < h and 0 <= x < w:
				if s[y][x] == '.' and vi[y][x] == -1:
					st.append([y, x])
				elif s[y][x] == '#':
					s2 = 1
				vi[y][x] = 1
		if s2 == 1:
			st2.append([h1, w1])
	while st2:
		(h1, w1) = st2.popleft()
		for m in d2:
			x = w1 + m[1]
			y = h1 + m[0]
			if 0 <= y < h and 0 <= x < w and (vi[y][x] == -1) and (s[y][x] == '.'):
				vi[y][x] = 1
				st.append([y, x])
	c += 1
print(-1)