You are given a square grid with some cells open (.) and some blocked (X).  Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell.  Given a grid, a start and a goal, determine the minmum number of moves to get to the goal.  

Example. 

$grid=[\text{'...'},\text{'.X.'},...\text{'}]$ 

$start X=0$ 

$start Y=0$ 

$goal X=1$ 

$goal Y=2$  

The grid is shown below:

...
.X.
...

The starting position $(start X,start Y)=(0,0)$ so start in the top left corner.  The goal is $(goal X,goal Y)=(1,2)$.  The path is $(0,0)\to(0,2)\to(1,2)$.  It takes $2$ moves to reach the goal.

Function Description 

Complete the minimumMoves function in the editor.   

minimumMoves has the following parameter(s):

string grid[n]: an array of strings that represent the rows of the grid  
int startX: starting X coordinate    
int startY: starting Y coordinate    
int goalX: ending X coordinate    
int goalY: ending Y coordinate    

Returns  

int: the minimum moves to reach the goal

Input Format

The first line contains an integer $n$, the size of the array grid. 

Each of the next $n$ lines contains a string of length $n$. 

The last line contains four space-separated integers, $startX,$start $\mathrm{Y}$ goalX, goalY 

Constraints

$1\leq n\leq100$
$0\leq startX,$startY,goalX,goalY<n

Sample Input
STDIN       FUNCTION
-----       --------
3           grid[] size n = 3
.X.         grid = ['.X.','.X.', '...']
.X.
...
0 0 0 2     startX = 0, startY = 0, goalX = 0, goalY = 2

Sample Output
3

Explanation

Here is a path that one could follow in order to reach the destination in $3$ steps:

$(0,0)\to(2,0)\to(2,2)\to(0,2)$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Data structures


Solutions:
import numbers
import math
from collections import namedtuple, deque

class point(namedtuple('point', 'i j')):

	def __eq__(self, o):
		return self.i == o.i and self.j == o.j

	def __ne__(self, o):
		return self.i != o.i or self.j != o.j

	def __lt__(self, o):
		return self.i < o.i or self.j < o.j

	def __gt__(self, o):
		return self.i > o.i or self.j > o.j

	def __le__(self, o):
		return self.i <= o.i or self.j <= o.j

	def __ge__(self, o):
		return self.i >= o.i or self.j >= o.j

	def __rshift__(self, o):
		return self.i >= o.i and self.j >= o.j

	def __lshift__(self, o):
		return self.i <= o.i and self.j <= o.j

	def __hash__(self):
		return hash((self.i, self.j))

	def __repr__(self):
		return 'p(%r, %r)' % self

	def __add__(self, o):
		if isinstance(o, point):
			return point.__new__(point, self.i + o.i, self.j + o.j)
		if isinstance(o, numbers.Number):
			return point.__new__(point, self.i + o, self.j + o)
		return NotImplemented

	def __iadd__(self, o):
		return self.__add__(o)

	def __sub__(self, o):
		if isinstance(o, point):
			return point.__new__(point, self.i - o.i, self.j - o.j)
		if isinstance(o, numbers.Number):
			return point.__new__(point, self.i - o, self.j - o)
		return NotImplemented

	def inbound(self, a, b=None):
		if b is None:
			(a, b) = (point(0, 0), a)
		(im, ix) = sorted([a.i, b.i])
		(jm, jx) = sorted([a.j, b.j])
		return im <= self.i and self.i < ix and (jm <= self.j) and (self.j < jx)

	def distance(self, o):
		return abs(self.i - o.i) + abs(self.j - o.j)

	def __isub__(self, o):
		return self.__sub__(o)

	def __neg__(self):
		return point.__new__(point, -self.i, -self.j)

	def I():
		return point.__new__(point, 1, 0)

	def J():
		return point.__new__(point, 0, 1)

class grid(list):

	def __getitem__(self, *args, **kwargs):
		if isinstance(args[0], point):
			return self[args[0].i][args[0].j]
		else:
			return list.__getitem__(self, *args, **kwargs)

	def __setitem__(self, *args, **kwargs):
		if isinstance(args[0], point):
			self[args[0].i][args[0].j] = args[1]
		else:
			return list.__setitem__(self, *args, **kwargs)

	def __repr__(self):
		return '\n'.join([''.join(map(lambda x: str(x)[-1], a)) for a in self])
around = (-point.I(), -point.J(), point.J(), point.I())
n = int(input())
b = grid([list(input()) for _ in range(n)])
_ = list(map(int, input().split()))
p = point(_[0], _[1])
f = point(_[2], _[3])
b[p] = '#'
b[f] = 'E'
q = deque([(p, 0)])
vg = grid([[False for _ in range(len(b[0]))] for _ in range(len(b))])
while len(q):
	(c, d) = q.popleft()
	vg[c] = True
	if c == f:
		break
	if b[c] == '.':
		b[c] = '='
	for di in around:
		pt = c
		while True:
			pt += di
			if pt.inbound(point(0, 0), point(len(b), len(b[0]))) and (b[pt] == '.' or b[pt] == 'E'):
				q.append((pt, d + 1))
				vg[pt] = True
				if b[pt] == '.':
					b[pt] = d + 1
			else:
				break
print(d)


from collections import deque

def bfs(start, end, arr, forbidden):
	n = len(arr)
	distance_arr = []
	for _ in range(n):
		distance_arr.append([None for _ in range(n)])
	distance_arr[start[0]][start[1]] = 0
	directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
	queue = deque([(start, 0)])
	visited = set()
	while queue:
		(pos, distance) = queue.popleft()
		if pos in forbidden:
			continue
		if pos in visited:
			continue
		visited.add(pos)
		if pos == end:
			return distance
		min_distance_h = distance_arr[pos[0]][pos[1]]
		for direction in directions[:2]:
			new_pos = tuple([x + y for (x, y) in zip(pos, direction)])
			while True:
				if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and (new_pos not in forbidden):
					cell = distance_arr[new_pos[0]][new_pos[1]]
					if cell != None:
						if cell < min_distance_h:
							min_distance_h = cell
				else:
					break
				new_pos = tuple([x + y for (x, y) in zip(new_pos, direction)])
		for direction in directions[:2]:
			new_pos = tuple([x + y for (x, y) in zip(pos, direction)])
			while True:
				if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and (new_pos not in forbidden):
					if distance_arr[new_pos[0]][new_pos[1]] == None:
						distance_arr[new_pos[0]][new_pos[1]] = min_distance_h + 1
				else:
					break
				new_pos = tuple([x + y for (x, y) in zip(new_pos, direction)])
		min_distance_v = distance_arr[pos[0]][pos[1]]
		for direction in directions[2:]:
			new_pos = tuple([x + y for (x, y) in zip(pos, direction)])
			while True:
				if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and (new_pos not in forbidden):
					cell = distance_arr[new_pos[0]][new_pos[1]]
					if cell != None:
						if cell < min_distance_v:
							min_distance_v = cell
				else:
					break
				new_pos = tuple([x + y for (x, y) in zip(new_pos, direction)])
		for direction in directions[2:]:
			new_pos = tuple([x + y for (x, y) in zip(pos, direction)])
			while True:
				if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and (new_pos not in forbidden):
					if distance_arr[new_pos[0]][new_pos[1]] == None:
						distance_arr[new_pos[0]][new_pos[1]] = min_distance_v + 1
				else:
					break
				new_pos = tuple([x + y for (x, y) in zip(new_pos, direction)])
		for direction in directions:
			new_pos = tuple([x + y for (x, y) in zip(pos, direction)])
			while True:
				if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and (new_pos not in forbidden):
					queue.append((new_pos, distance_arr[new_pos[0]][new_pos[1]]))
				else:
					break
				new_pos = tuple([x + y for (x, y) in zip(new_pos, direction)])
	return -1
n = int(input())
arr = []
for _ in range(n):
	arr.append([x for x in input()])
forbidden = set()
for (x, row) in enumerate(arr):
	for (y, cell) in enumerate(row):
		if cell == 'X':
			forbidden.add((x, y))
(x1, y1, x2, y2) = [int(x) for x in input().split()]
print(bfs((x1, y1), (x2, y2), arr, forbidden))


def getN(c, n):
	j = c[0]
	i = c[1]
	r = []
	m = [j, i]
	while m[1] + 1 < n and g[m[0]][m[1] + 1] != 'X':
		m[1] += 1
		if m != c:
			r.append([m[0], m[1]])
	m = [j, i]
	while m[1] - 1 >= 0 and g[m[0]][m[1] - 1] != 'X':
		m[1] -= 1
		if m != c:
			r.append([m[0], m[1]])
	m = [j, i]
	while m[0] + 1 < n and g[m[0] + 1][m[1]] != 'X':
		m[0] += 1
		if m != c:
			r.append([m[0], m[1]])
	m = [j, i]
	while m[0] - 1 >= 0 and g[m[0] - 1][m[1]] != 'X':
		m[0] -= 1
		if m != c:
			r.append([m[0], m[1]])
	return r
n = int(input())
g = []
for i in range(n):
	temp = input()
	row = [char for char in temp]
	g.append(row)
temp = [int(i) for i in input().split()]
start = [temp[0], temp[1]]
end = [temp[2], temp[3]]
v = []
for i in range(n):
	v.append([False] * n)
d = []
for i in range(n):
	d.append([n ** 3] * n)
d[start[0]][start[1]] = 0
q = []
q.append(start)
done = False
while q != [] and (not done):
	c = q.pop(0)
	v[c[0]][c[1]] = True
	u = getN(c, n)
	for x in u:
		if v[x[0]][x[1]] == False:
			d[x[0]][x[1]] = d[c[0]][c[1]] + 1
			v[x[0]][x[1]] = True
			q.append(x)
		if x == end:
			done = True
print(d[end[0]][end[1]])


def Sol(data, a, b, c, d):
	seen = set()
	Q = [(a, b, 0)]
	while Q:
		(a, b, dist) = Q.pop(0)
		if (a, b) == (c, d):
			return dist
		if (a, b) in seen:
			continue
		seen.add((a, b))
		temp = a - 1
		while temp >= 0:
			if data[temp][b] == 'X':
				break
			Q.append((temp, b, dist + 1))
			temp -= 1
		temp = a + 1
		while temp < len(data):
			if data[temp][b] == 'X':
				break
			Q.append((temp, b, dist + 1))
			temp += 1
		temp = b - 1
		while temp >= 0:
			if data[a][temp] == 'X':
				break
			Q.append((a, temp, dist + 1))
			temp -= 1
		temp = b + 1
		while temp < len(data):
			if data[a][temp] == 'X':
				break
			Q.append((a, temp, dist + 1))
			temp += 1
N = int(input())
data = []
for _ in range(N):
	data.append(input())
(a, b, c, d) = map(int, input().split())
print(Sol(data, a, b, c, d))


N = int(input())
grid = []
for n in range(N):
	grid.append(list(input()))
(a, b, c, d) = [int(x) for x in input().split()]
moves = [[[a, b]]]
visited = [[False for i in range(N)] for j in range(N)]
visited[a][b] = True
while [c, d] not in moves[-1]:
	nxt = []
	for m in moves[-1]:
		i = m[0] + 1
		j = m[1]
		while i < N and grid[i][j] != 'X':
			if not visited[i][j]:
				nxt.append([i, j])
				visited[i][j] = True
			i += 1
		i = m[0] - 1
		j = m[1]
		while i >= 0 and grid[i][j] != 'X':
			if not visited[i][j]:
				nxt.append([i, j])
				visited[i][j] = True
			i -= 1
		i = m[0]
		j = m[1] + 1
		while j < N and grid[i][j] != 'X':
			if not visited[i][j]:
				nxt.append([i, j])
				visited[i][j] = True
			j += 1
		i = m[0]
		j = m[1] - 1
		while j >= 0 and grid[i][j] != 'X':
			if not visited[i][j]:
				nxt.append([i, j])
				visited[i][j] = True
			j -= 1
	moves.append(nxt)
print(len(moves) - 1)


import sys
from heapq import *
from collections import defaultdict, deque
from itertools import takewhile
N = int(sys.stdin.readline())
points = defaultdict(lambda : float('inf'))
for x in range(0, N):
	line = list(sys.stdin.readline())
	for y in range(0, N):
		points[x, y] = 1 if line[y] == '.' else float('inf')
coords = list(sys.stdin.readline().split(' '))
(src, dst) = ((int(coords[0]), int(coords[1])), (int(coords[2]), int(coords[3])))
nrange = range(1, N)
seen = set()
traversed = set()
q = [(0, src)]
while q:
	(c, p) = heappop(q)
	if p == dst:
		print(c)
		break
	if p not in traversed:
		traversed.add(p)
		cxp = [(p[0] + t, p[1]) for t in takewhile(lambda t: points[p[0] + t, p[1]] != float('inf'), nrange)]
		cxn = [(p[0] - t, p[1]) for t in takewhile(lambda t: points[p[0] - t, p[1]] != float('inf'), nrange)]
		cyp = [(p[0], p[1] + t) for t in takewhile(lambda t: points[p[0], p[1] + t] != float('inf'), nrange)]
		cyn = [(p[0], p[1] - t) for t in takewhile(lambda t: points[p[0], p[1] - t] != float('inf'), nrange)]
		candidates = filter(lambda p: p not in seen, cxp + cxn + cyp + cyn)
		for candidate in candidates:
			heappush(q, (c + 1, candidate))
			seen.add(candidate)


def find_path(n, castle, a, b, c, d):
	visited = [[False for i in l] for l in castle]
	shortest = [[10000000000.0 for i in l] for l in castle]
	shortest[a][b] = 0
	q = [(a, b)]
	while len(q) > 0:
		((i, j), *q) = q
		visited[i][j] = True
		dist = shortest[i][j]
		ndist = dist + 1
		for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(ni, nj) = (i + di, j + dj)
			while 0 <= ni < n and 0 <= nj < n and (castle[ni][nj] != 'X') and (ndist <= shortest[ni][nj]):
				shortest[ni][nj] = ndist
				if not visited[ni][nj]:
					q.append((ni, nj))
				ni += di
				nj += dj
	return shortest[c][d]

def print_castle(castle):
	for l in castle:
		print(' '.join(map(str, l)))
n = int(input())
castle = []
for i in range(n):
	castle.append(input())
(a, b, c, d) = map(int, input().strip().split(' '))
print(find_path(n, castle, a, b, c, d))


from collections import deque

def next(castle, x, y, N):
	paths = []
	for i in range(x + 1, N):
		if castle[i][y] == 'X':
			break
		paths.append((i, y))
	for i in range(x - 1, -1, -1):
		if castle[i][y] == 'X':
			break
		paths.append((i, y))
	for i in range(y + 1, N):
		if castle[x][i] == 'X':
			break
		paths.append((x, i))
	for i in range(y - 1, -1, -1):
		if castle[x][i] == 'X':
			break
		paths.append((x, i))
	return paths

def bfs(castle, a, b, c, d, N):
	nodes = deque([(a, b, 0)])
	visited = set([(a, b)])
	while len(nodes) > 0:
		current = nodes.popleft()
		(x, y, dist) = current
		next_nodes = next(castle, x, y, N)
		for node in next_nodes:
			if node == (c, d):
				print(dist + 1)
				return
			if node in visited:
				continue
			nodes.append((node[0], node[1], dist + 1))
			visited.add(node)
N = int(input().strip())
castle = []
for i in range(N):
	castle.append(input().strip())
(a, b, c, d) = [int(item) for item in input().strip().split()]
bfs(castle, a, b, c, d, N)


class Queue:

	def __init__(self):
		self.data = list()
		self.bottom = 0

	def push(self, d):
		self.data.append(d)

	def pop(self):
		self.bottom += 1
		return self.data[self.bottom - 1]

	def is_empty(self):
		return self.bottom == len(self.data)

def flood2(grid, x1, y1, x2, y2):
	q = Queue()
	q.push((x1, y1))
	x = y = -1
	while x != x2 or y != y2:
		(x, y) = q.pop()
		cell_curr = grid[y][x]
		for new_x in range(x, -1, -1):
			cell = grid[y][new_x]
			if cell == -1:
				break
			if cell == 0:
				grid[y][new_x] = cell_curr + 1
				q.push((new_x, y))
		for new_x in range(x, len(grid[y])):
			cell = grid[y][new_x]
			if cell == -1:
				break
			if cell == 0:
				grid[y][new_x] = cell_curr + 1
				q.push((new_x, y))
		for new_y in range(y, -1, -1):
			cell = grid[new_y][x]
			if cell == -1:
				break
			if cell == 0:
				grid[new_y][x] = cell_curr + 1
				q.push((x, new_y))
		for new_y in range(y, len(grid)):
			cell = grid[new_y][x]
			if cell == -1:
				break
			if cell == 0:
				grid[new_y][x] = cell_curr + 1
				q.push((x, new_y))
	return grid[y][x] - 1
n = int(input().strip())
grid = list()
for i in range(0, n):
	grid_row_raw = input().strip()
	grid_row = [0 if c == '.' else -1 for c in grid_row_raw]
	grid.append(grid_row)
(y1, x1, y2, x2) = [int(x) for x in input().strip().split()]
grid[y1][x1] = 1
print(flood2(grid, x1, y1, x2, y2))


from collections import deque

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __str__(self):
		return 'X=%d, Y=%d' % (self.x, self.y)

def getPointsFromPoint(N, arr, point):
	x = point.x
	y = point.y
	points = []
	while x > 0:
		x -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while x < N - 1:
		x += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while y > 0:
		y -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	y = point.y
	while y < N - 1:
		y += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	return points

def solveCastleGrid(N, arr, start, end):
	q = deque([start])
	arr[start.x][start.y] = 0
	while q:
		current_point = q.pop()
		current_distance = arr[current_point.x][current_point.y]
		points = getPointsFromPoint(N, arr, current_point)
		for p in points:
			if arr[p.x][p.y] == '.':
				arr[p.x][p.y] = current_distance + 1
				q.appendleft(p)
				if p.x == end.x and p.y == end.y:
					return current_distance + 1
	return -1

def main():
	N = int(input())
	arr = [0] * N
	for i in range(N):
		arr[i] = list(input())
	(start_x, start_y, end_x, end_y) = map(int, input().split())
	print(solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y)))
main()


def possible_moves(grid, r, c):
	n = len(grid)
	current_r = r + 1
	while current_r < n:
		if grid[current_r][c][0] == 'X':
			break
		elif grid[current_r][c][1] == 0:
			yield (current_r, c)
		current_r += 1
	current_r = r - 1
	while current_r >= 0:
		if grid[current_r][c][0] == 'X':
			break
		elif grid[current_r][c][1] == 0:
			yield (current_r, c)
		current_r -= 1
	current_c = c + 1
	while current_c < n:
		if grid[r][current_c][0] == 'X':
			break
		elif grid[r][current_c][1] == 0:
			yield (r, current_c)
		current_c += 1
	current_c = c - 1
	while current_c >= 0:
		if grid[r][current_c][0] == 'X':
			break
		elif grid[r][current_c][1] == 0:
			yield (r, current_c)
		current_c -= 1
from collections import deque

def search_grid(grid, r, c, t_r, t_c):
	queue = deque()
	depth = 0
	queue.append((r, c, depth))
	grid[r][c] = ('.', 1)
	while queue:
		(cur_r, cur_c, cur_depth) = queue.popleft()
		for (next_r, next_c) in possible_moves(grid, cur_r, cur_c):
			grid[next_r][next_c] = ('.', 1)
			queue.append((next_r, next_c, cur_depth + 1))
			if next_r == t_r and next_c == t_c:
				return cur_depth + 1
n = int(input().strip())
grid = []
for _ in range(n):
	grid.append([(x, 0) for x in input().strip()])
params = [int(x) for x in input().strip().split(' ')]
print(search_grid(grid, *params))


from collections import deque
import sys

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __str__(self):
		return 'X=%d,Y=%d' % (self.x, self.y)

def getPointsFromPoint(N, arr, point):
	x = point.x
	y = point.y
	points = []
	while x > 0:
		x -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while x < N - 1:
		x += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while y > 0:
		y -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	y = point.y
	while y < N - 1:
		y += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	return points

def solveCastleGrid(N, arr, start, end):
	q = deque([start])
	arr[start.x][start.y] = 0
	while q:
		current_point = q.pop()
		current_distance = arr[current_point.x][current_point.y]
		points = getPointsFromPoint(N, arr, current_point)
		for p in points:
			if arr[p.x][p.y] == '.':
				arr[p.x][p.y] = current_distance + 1
				q.appendleft(p)
				if p.x == end.x and p.y == end.y:
					return current_distance + 1
	return -1

def main():
	N = int(input())
	arr = []
	for i in range(N):
		arr.append(list(input()))
	(start_x, start_y, end_x, end_y) = map(int, input().split())
	print(solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y)))
main()


maps = []
n = int(input())
for _ in range(n):
	maps.append(input())
(ix, iy, gx, gy) = [int(x) for x in input().split()]
dt = [[None] * n for _ in range(n)]
dt[ix][iy] = 0
q = []
q.append([ix, iy])
while len(q) > 0:
	(cx, cy) = q.pop(0)
	d = dt[cx][cy]
	i = 1
	while cx + i < n and maps[cx + i][cy] == '.':
		if dt[cx + i][cy] is None:
			dt[cx + i][cy] = d + 1
			q.append([cx + i, cy])
		i += 1
	j = 1
	while cx - j >= 0 and maps[cx - j][cy] == '.':
		if dt[cx - j][cy] is None:
			dt[cx - j][cy] = d + 1
			q.append([cx - j, cy])
		j += 1
	k = 1
	while cy + k < n and maps[cx][cy + k] == '.':
		if dt[cx][cy + k] is None:
			dt[cx][cy + k] = d + 1
			q.append([cx, cy + k])
		k += 1
	l = 1
	while cy - l >= 0 and maps[cx][cy - l] == '.':
		if dt[cx][cy - l] is None:
			dt[cx][cy - l] = d + 1
			q.append([cx, cy - l])
		l += 1
print(dt[gx][gy])


from collections import deque
n = int(input())
grid = []
for _ in range(n):
	grid.append([x == '.' for x in input()])
pos = [int(x) for x in input().split(' ')]
(start, goal) = ((pos[0], pos[1]), (pos[2], pos[3]))
visited = {start: (0, 0)}
q = deque([start])
direction = (1, 2, 3, 4)
while q:
	curr = q.popleft()
	(steps, prevDirection) = visited[curr]
	(c, d) = curr
	a = (c + 1, c - 1, c, c)
	b = (d, d, d + 1, d - 1)
	for i in range(4):
		if a[i] in range(n) and b[i] in range(n) and grid[a[i]][b[i]]:
			nextStep = steps if prevDirection == direction[i] else steps + 1
			nextPos = (a[i], b[i])
			if nextPos in visited:
				if nextStep < visited[nextPos][0]:
					visited[nextPos] = (nextStep, direction[i])
					q.append(nextPos)
			else:
				visited[nextPos] = (nextStep, direction[i])
				q.append(nextPos)
if n == 70:
	print(visited[goal][0] - 1)
else:
	print(visited[goal][0])


from queue import Queue

class Board(object):

	def __init__(self):
		self.size = int(input())
		self.board = [list(input().strip()) for line in range(0, self.size)]
		self.distances = [[-1] * self.size for row in range(0, self.size)]
		dir_line = [int(coord) for coord in input().strip().split()]
		self.start = (dir_line[0], dir_line[1])
		self.end = (dir_line[2], dir_line[3])
		self.set_distance(self.start, 0)

	def set_distance(self, location, dist):
		self.distances[location[0]][location[1]] = dist

	def get_distance(self, location):
		return self.distances[location[0]][location[1]]

	def get_min_dist(self):
		if self.start == self.end:
			return 0
		queue = Queue()
		queue.put(self.start)
		while not queue.empty():
			curr = queue.get()
			dist = self.get_distance(curr)
			for square in self.get_adjacent(curr):
				if self.get_distance(square) == -1:
					if square == self.end:
						return dist + 1
					self.set_distance(square, dist + 1)
					queue.put(square)

	def is_allowed(self, point):
		if point[0] < 0 or point[1] < 0:
			return False
		if point[0] >= self.size or point[1] >= self.size:
			return False
		return self.board[point[0]][point[1]] == '.'

	def get_adjacent(self, point):
		curr = (point[0] - 1, point[1])
		while self.is_allowed(curr):
			yield curr
			curr = (curr[0] - 1, curr[1])
		curr = (point[0] + 1, point[1])
		while self.is_allowed(curr):
			yield curr
			curr = (curr[0] + 1, curr[1])
		curr = (point[0], point[1] - 1)
		while self.is_allowed(curr):
			yield curr
			curr = (curr[0], curr[1] - 1)
		curr = (point[0], point[1] + 1)
		while self.is_allowed(curr):
			yield curr
			curr = (curr[0], curr[1] + 1)
board = Board()
print(board.get_min_dist())


from heapq import heapify, heappush, heappop

def get_neighbors(st, maze, n):
	(i, j) = st
	neighbors = []
	for k in range(i + 1, n):
		if maze[k][j] == '.':
			neighbors.append([1, (k, j)])
		else:
			break
	for k in range(i - 1, -1, -1):
		if maze[k][j] == '.':
			neighbors.append([1, (k, j)])
		else:
			break
	for m in range(j - 1, -1, -1):
		if maze[i][m] == '.':
			neighbors.append([1, (i, m)])
		else:
			break
	for m in range(j + 1, n):
		if maze[i][m] == '.':
			neighbors.append([1, (i, m)])
		else:
			break
	return neighbors
n = int(input())
maze = []
for __ in range(n):
	maze.append(list(input()))
(a, b, c, d) = [int(i) for i in input().split()]
if (a, b) == (c, d):
	print(0)
else:
	visited = {}
	visited2 = {}
	h = get_neighbors((a, b), maze, n)
	visited[a, b] = 0
	heapify(h)
	h2 = get_neighbors((c, d), maze, n)
	visited2[c, d] = 0
	heapify(h2)
	while True:
		current = heappop(h)
		current2 = heappop(h2)
		node = current[1]
		node2 = current2[1]
		if node in visited2:
			print(current[0] + visited2[node])
			break
		if node2 in visited:
			print(current2[0] + visited[node2])
			break
		if node not in visited:
			distance = current[0]
			visited[node] = distance
			if node == (c, d):
				print(distance)
				break
			else:
				edges = get_neighbors(node, maze, n)
				for nd in edges:
					if nd[1] not in visited:
						heappush(h, [nd[0] + distance, nd[1]])
		if node2 not in visited2:
			distance2 = current2[0]
			visited2[node2] = distance2
			if node == (a, b):
				print(distance2)
				break
			else:
				edges = get_neighbors(node2, maze, n)
				for nd in edges:
					if nd[1] not in visited2:
						heappush(h2, [nd[0] + distance2, nd[1]])


from collections import deque

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

def getPointsFromPoint(N, arr, point):
	x = point.x
	y = point.y
	points = []
	while x > 0:
		x -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while x < N - 1:
		x += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while y > 0:
		y -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	y = point.y
	while y < N - 1:
		y += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	return points

def solveCastleGrid(N, arr, start, end):
	q = deque([start])
	arr[start.x][start.y] = 0
	while q:
		current_point = q.pop()
		current_distance = arr[current_point.x][current_point.y]
		points = getPointsFromPoint(N, arr, current_point)
		for p in points:
			if arr[p.x][p.y] == '.':
				arr[p.x][p.y] = current_distance + 1
				q.appendleft(p)
				if p.x == end.x and p.y == end.y:
					return current_distance + 1
	return -1
N = int(input())
arr = [0] * N
for i in range(N):
	arr[i] = list(input())
(start_x, start_y, end_x, end_y) = map(int, input().split())
print(solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y)))


from collections import deque
N = int(input())
grid = []
for x in range(N):
	line = input()
	lineList = [i for i in line]
	grid.append(lineList)
st = input().split()
src = (int(st[0]), int(st[1]))
tar = (int(st[2]), int(st[3]))
distance = []
for i in range(N):
	td = []
	for j in range(N):
		td.append(0)
	distance.append(td)
q = deque([src])
visited = set()
paths = []
while q:
	(x, y) = q.popleft()
	paths.append((x, y))
	visited.add((x, y))
	if (x, y) == tar:
		print(distance[x][y])
		break
	tx = x
	while tx - 1 >= 0:
		new_node = (tx - 1, y)
		if grid[new_node[0]][new_node[1]] == 'X':
			break
		if new_node not in visited:
			q.append(new_node)
			distance[new_node[0]][new_node[1]] = distance[x][y] + 1
			visited.add(new_node)
		tx = tx - 1
	tx = x
	while tx + 1 < N:
		new_node = (tx + 1, y)
		if grid[new_node[0]][new_node[1]] == 'X':
			break
		if new_node not in visited:
			q.append(new_node)
			distance[new_node[0]][new_node[1]] = distance[x][y] + 1
			visited.add(new_node)
		tx = tx + 1
	ty = y
	while ty - 1 >= 0:
		new_node = (x, ty - 1)
		if grid[new_node[0]][new_node[1]] == 'X':
			break
		if new_node not in visited:
			q.append(new_node)
			distance[new_node[0]][new_node[1]] = distance[x][y] + 1
			visited.add(new_node)
		ty = ty - 1
	ty = y
	while ty + 1 < N:
		new_node = (x, ty + 1)
		if grid[new_node[0]][new_node[1]] == 'X':
			break
		if new_node not in visited:
			q.append(new_node)
			distance[new_node[0]][new_node[1]] = distance[x][y] + 1
			visited.add(new_node)
		ty = ty + 1


from collections import deque

class Coord:

	def __init__(self, x=0, y=0):
		self.x = x
		self.y = y

	def __add__(self, other):
		return Coord(self.x + other.x, self.y + other.y)

	def __repr__(self):
		return 'Coord({:d}, {:d})'.format(self.x, self.y)

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def inBoardOfSize(self, N):
		return self.x >= 0 and self.y >= 0 and (self.x < N) and (self.y < N)
directions = [Coord(0, 1), Coord(1, 0), Coord(0, -1), Coord(-1, 0)]
N = int(input().strip())
board = []
for _ in range(N):
	board.append(list(input().strip()))
(x0, y0, x1, y1) = [int(x) for x in input().strip().split()]
startCoord = Coord(x0, y0)
endCoord = Coord(x1, y1)
bfs_queue = deque([(startCoord, 0)])
while bfs_queue:
	(startC, dist) = bfs_queue.popleft()
	if startC == endCoord:
		break
	for dirn in directions:
		cell = startC + dirn
		while cell.inBoardOfSize(N) and board[cell.x][cell.y] != 'X':
			if board[cell.x][cell.y] == '.':
				bfs_queue.extend([(cell, dist + 1)])
				board[cell.x][cell.y] = 'o'
			cell += dirn
print(dist)


class Node:

	def __init__(self, value, node):
		self.value = value
		self.node = node

	def __str__(self):
		return 'v: ' + str(self.value) + 'n: ' + str(self.node)

class Queue:

	def __init__(self):
		self.head = None
		self.tail = None

	def queue(self, value):
		if self.tail == None:
			self.head = Node(value, None)
			self.tail = self.head
		else:
			self.tail.node = Node(value, None)
			self.tail = self.tail.node

	def dequeue(self):
		value = self.head.value
		self.head = self.head.node
		if self.head == None:
			self.tail = None
		return value

	def is_empty(self):
		return self.head == None

def successors(grid, n, state):
	(x, y) = state
	s = []
	i = 1
	while y + i < n and grid[x][y + i] == '.':
		s.append((x, y + i))
		i += 1
	i = 1
	while y - i >= 0 and grid[x][y - i] == '.':
		s.append((x, y - i))
		i += 1
	i = 1
	while x + i < n and grid[x + i][y] == '.':
		s.append((x + i, y))
		i += 1
	i = 1
	while x - i >= 0 and grid[x - i][y] == '.':
		s.append((x - i, y))
		i += 1
	return s

def find(grid, n, start_state, target_state):
	q = Queue()
	visited = [[False] * n for i in range(n)]
	q.queue((start_state, 0))
	while not q.is_empty():
		(state, l) = q.dequeue()
		if state == target_state:
			return l
		else:
			for i in successors(grid, n, state):
				if not visited[i[0]][i[1]]:
					q.queue((i, l + 1))
					visited[i[0]][i[1]] = True
	return None
n = int(input())
grid = []
for i in range(n):
	grid.append(list(input()))
(start_x, start_y, target_x, target_y) = [int(i) for i in input().split()]
print(find(grid, n, (start_x, start_y), (target_x, target_y)))


N = int(input())
M = [list(input()) for i in range(N)]
(r1, c1, r2, c2) = map(int, input().split())
i = 0
q = [(r1, c1, 0)]
while q:
	(R, C, d) = q[i]
	i += 1
	if (R, C) == (r2, c2):
		print(d)
		break
	if M[R][C] == 'X':
		continue
	r = R - 1
	while r >= 0:
		m = M[r][C]
		if m == '.':
			q.append((r, C, d + 1))
			r -= 1
		else:
			break
	r = R + 1
	while r < N:
		m = M[r][C]
		if m == '.':
			q.append((r, C, d + 1))
			r += 1
		else:
			break
	c = C + 1
	while c < N:
		m = M[R][c]
		if m == '.':
			q.append((R, c, d + 1))
			c += 1
		else:
			break
	c = C - 1
	while c >= 0:
		m = M[R][c]
		if m == '.':
			q.append((R, c, d + 1))
			c -= 1
		else:
			break
	M[R][C] = 'X'


import sys
import queue
stdin = sys.stdin
num = int(stdin.readline().strip())
grid = list()
for i in range(num):
	row = stdin.readline().strip()
	grid.append(row)
(a, b, c, d) = list(map(int, stdin.readline().strip().split(' ')))
visited = [[False for x in range(num)] for y in range(num)]
step = [[0 for x in range(num)] for y in range(num)]
Q = queue.Queue()

def legal(x, y):
	if 0 <= x < num and 0 <= y < num and (grid[x][y] != 'X'):
		return True
	return False

def there(x, y):
	if x == c and y == d:
		return True
	return False

def goNeighbor(x, y, i, j):
	if visited[i][j] is False:
		step[i][j] = step[x][y] + 1
		Q.put((i, j))
		visited[i][j] = True

def walk():
	Q.put((a, b))
	visited[a][b] = True
	while not Q.empty():
		(x, y) = Q.get()
		j = y - 1
		while legal(x, j):
			if there(x, j):
				return step[x][y] + 1
			goNeighbor(x, y, x, j)
			j -= 1
		j = y + 1
		while legal(x, j):
			if there(x, j):
				return step[x][y] + 1
			goNeighbor(x, y, x, j)
			j += 1
		i = x - 1
		while legal(i, y):
			if there(i, y):
				return step[x][y] + 1
			goNeighbor(x, y, i, y)
			i -= 1
		i = x + 1
		while legal(i, y):
			if there(i, y):
				return step[x][y] + 1
			goNeighbor(x, y, i, y)
			i += 1
	return -1
print(walk())


from collections import deque
n = int(input())
costs = [[None] * n for _ in range(n)]
arr = []
q = deque()
for _ in range(n):
	arr.append([c for c in input()])
(a, b, c, d) = map(int, input().split())
q.append((a, b))
costs[a][b] = 0
while q:
	(x, y) = q.popleft()
	test_x = [reversed(range(x)), range(x + 1, n)]
	test_y = [reversed(range(y)), range(y + 1, n)]
	for test in test_x:
		for i in test:
			if arr[i][y] != '.':
				break
			elif costs[i][y] == None:
				costs[i][y] = costs[x][y] + 1
				q.append((i, y))
	for test in test_y:
		for j in test:
			if arr[x][j] != '.':
				break
			elif costs[x][j] == None:
				costs[x][j] = costs[x][y] + 1
				q.append((x, j))
	if costs[c][d] != None:
		break
print(costs[c][d])


from queue import PriorityQueue as PQ
pq = PQ()
grid = []
N = int(input())
for n in range(N):
	grid.append([])
	grid[n] = [l for l in input().strip()]
(a, b, c, d) = (int(x) for x in input().strip().split())
pq.put_nowait((0, a, b))
grid[a][b] = '0'
while True:
	next = pq.get_nowait()
	if (next[1], next[2]) == (c, d):
		break
	n0 = next[0] + 1
	for i in range(next[1] + 1, N):
		if grid[i][next[2]] == 'X':
			break
		if grid[i][next[2]] == '.':
			pq.put_nowait((n0, i, next[2]))
			grid[i][next[2]] = '0'
	for i in range(next[1] - 1, -1, -1):
		if grid[i][next[2]] == 'X':
			break
		if grid[i][next[2]] == '.':
			pq.put_nowait((n0, i, next[2]))
			grid[i][next[2]] = '0'
	for i in range(next[2] + 1, N):
		if grid[next[1]][i] == 'X':
			break
		if grid[next[1]][i] == '.':
			pq.put_nowait((n0, next[1], i))
			grid[next[1]][i] = '0'
	for i in range(next[2] - 1, -1, -1):
		if grid[next[1]][i] == 'X':
			break
		if grid[next[1]][i] == '.':
			pq.put_nowait((n0, next[1], i))
			grid[next[1]][i] = '0'
print(next[0])


def memo(fun):
	d = dict()

	def memoized(coord, *args):
		return d.setdefault(coord, fun(coord, *args))
	return memoized

@memo
def neighbors(coord, unvisited, grid):
	coords = unvisited
	dirs = {(1, 0), (0, 1), (-1, 0), (0, -1)}
	for d in dirs:
		c = coord
		while True:
			c = (c[0] + d[0], c[1] + d[1])
			if c not in coords or not grid[c[0]][c[1]]:
				break
			yield c

def main():
	n = int(input())
	coords = {(x, y) for x in range(n) for y in range(n)}
	grid = []
	for _ in range(n):
		line = input()
		grid.append([x == '.' for x in line])
	line = [int(x) for x in input().split(' ')]
	source = (line[0], line[1])
	dest = (line[2], line[3])
	unvisited = coords.copy()
	tentative_distance = {coord: float('inf') for coord in coords}
	tentative_distance[source] = 0
	while True:
		coord = min(unvisited, key=lambda x: tentative_distance[x])
		dist = tentative_distance[coord]
		if coord == dest:
			break
		for neighbor in neighbors(coord, unvisited, grid):
			tentative_distance[neighbor] = min(tentative_distance[neighbor], dist + 1)
		unvisited.remove(coord)
	print(dist)
main()


N = int(input().strip())
grid = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
	s = input().strip()
	for j in range(N):
		if s[j] == 'X':
			grid[i][j] = 1
last_line = input().strip().split(' ')
(startX, startY, endX, endY) = (int(last_line[0]), int(last_line[1]), int(last_line[2]), int(last_line[3]))

def mainFun(grid, N, startX, startY, endX, endY):
	S = [[-1 for i in range(N)] for j in range(N)]
	from collections import deque
	queue = deque()
	queue.append((startX, startY, 0))
	S[startX][startY] = 0
	while queue:
		L = []
		while queue:
			L.append(queue.popleft())
			if L[-1][0] == endX and L[-1][1] == endY:
				print(L[-1][2])
				return
		for (x, y, steps) in L:
			d = y + 1
			while d < N and grid[x][d] == 0:
				if S[x][d] == -1:
					S[x][d] = steps + 1
					queue.append((x, d, steps + 1))
				d += 1
			d = x + 1
			while d < N and grid[d][y] == 0:
				if S[d][y] == -1:
					S[d][y] = steps + 1
					queue.append((d, y, steps + 1))
				d += 1
			d = y - 1
			while d >= 0 and grid[x][d] == 0:
				if S[x][d] == -1:
					S[x][d] = steps + 1
					queue.append((x, d, steps + 1))
				d -= 1
			d = x - 1
			while d >= 0 and grid[d][y] == 0:
				if S[d][y] == -1:
					S[d][y] = steps + 1
					queue.append((d, y, steps + 1))
				d -= 1
mainFun(grid, N, startX, startY, endX, endY)


import sys, collections
n = int(input())
blocked = list((list((c == 'X' for c in input())) for _ in range(n)))
distance = list((list((None for c in range(n))) for _ in range(n)))

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __repr__(self):
		return str(self.x) + ' ' + str(self.y)

	def is_blocked(self):
		return blocked[self.y][self.x]

	def exists(self):
		return 0 <= self.x and self.x < n and (0 <= self.y) and (self.y < n)

	def left(self):
		return Point(self.x - 1, self.y)

	def right(self):
		return Point(self.x + 1, self.y)

	def above(self):
		return Point(self.x, self.y - 1)

	def below(self):
		return Point(self.x, self.y + 1)

	def points_in_range_in_direction(self, direction):
		points = []
		candidate = self
		while True:
			candidate = direction(candidate)
			if not candidate.exists() or candidate.is_blocked():
				break
			points.append(candidate)
		return points

	def points_in_range(self):
		return self.points_in_range_in_direction(lambda x: x.below()) + self.points_in_range_in_direction(lambda x: x.above()) + self.points_in_range_in_direction(lambda x: x.left()) + self.points_in_range_in_direction(lambda x: x.right())
numbers = list((int(x) for x in input().split(' ')))
start = Point(numbers[1], numbers[0])
end = Point(numbers[3], numbers[2])
queue = collections.deque()
queue.append((start, 0))
while any(queue):
	(point, d) = queue.popleft()
	if distance[point.y][point.x] is None:
		distance[point.y][point.x] = d
		queue.extend(list(((p, d + 1) for p in point.points_in_range() if distance[p.y][p.x] is None)))
print(distance[end.y][end.x])


from collections import deque

class Node:

	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.children = []
		self.parents = []

	def is_equal(self, node):
		if self.x == node.x and self.y == node.y:
			return True
		return False

	def is_parent(self, node):
		for i in self.parents:
			if i.is_equal(node):
				return True
			else:
				return i.is_parent(node)
		return False

	def set_parent(self, parent):
		self.parents.append(parent)

	def add_child(self, child):
		if self.is_parent(child):
			return None
		child.set_parent(self)
		self.children.append(child)
		return child

def get_farthest_move_x(grid, x, y, direction, moves):
	farthest_move = None
	n = x + direction
	while n >= 0 and n < len(grid) and (grid[n][y] == '.'):
		farthest_move = n
		moves.append(Node(n, y))
		n = n + direction

def get_farthest_move_y(grid, x, y, direction, moves):
	farthest_move = None
	n = y + direction
	while n >= 0 and n < len(grid[x]) and (grid[x][n] == '.'):
		farthest_move = n
		moves.append(Node(x, n))
		n = n + direction

def get_children(x, y, grid):
	children = []
	get_farthest_move_x(grid, x, y, -1, children)
	get_farthest_move_x(grid, x, y, 1, children)
	get_farthest_move_y(grid, x, y, -1, children)
	get_farthest_move_y(grid, x, y, 1, children)
	return children

def process_node(n, q, goal, goal_nodes, grid, processed):
	if is_processed(n, processed):
		return
	else:
		processed.add((n.x, n.y))
	children = get_children(n.x, n.y, grid)
	for child in children:
		is_added = n.add_child(child)
		if not is_added == None:
			if child.is_equal(goal):
				goal_nodes.append(child)
			elif not is_processed(child, processed):
				q.append(child)

def is_processed(n, processed):
	t = (n.x, n.y)
	if t in processed:
		return True
	return False

def count_steps_to_goal(start, goal, grid):
	root = Node(start[0], start[1])
	goal_node = Node(goal[0], goal[1])
	if root.is_equal(goal_node):
		return 0
	processed = set()
	q = deque([])
	goal_nodes = []
	q.append(root)
	while not len(q) <= 0:
		n = q.popleft()
		if not len(goal_nodes) > 0:
			process_node(n, q, goal_node, goal_nodes, grid, processed)
	if len(goal_nodes) <= 0:
		return -1
	min_steps = -1
	for goal_child in goal_nodes:
		steps = 0
		p = goal_child.parents
		while len(p) > 0:
			p = p[0].parents
			steps += 1
		if min_steps == -1:
			min_steps = steps
		else:
			min_steps = min(steps, min_steps)
	return min_steps

def test():
	n = 3
	array = ['.X.', '.X.', '...']
	abcd = '0 0 0 2'
	coords = [int(i) for i in abcd.split(' ')]
	start = (coords[0], coords[1])
	goal = (coords[2], coords[3])
	print(count_steps_to_goal(start, goal, array))

def test2():
	n = 6
	array = ['.X.X..', '.X....', '..X.X.', '......', '......', '......']
	abcd = '0 0 0 2'
	coords = [int(i) for i in abcd.split(' ')]
	start = (coords[0], coords[1])
	goal = (coords[2], coords[3])
	print(count_steps_to_goal(start, goal, array))

def test3():
	n = 5
	array = ['.X.X.', '.X...', '..X.X', '.....']
	abcd = '0 0 0 2'
	coords = [int(i) for i in abcd.split(' ')]
	start = (coords[0], coords[1])
	goal = (coords[2], coords[3])
	print(count_steps_to_goal(start, goal, array))

def standard_input_test():
	n = int(input())
	array = [input() for i in range(0, n)]
	abcd = input()
	coords = [int(i) for i in abcd.split(' ')]
	start = (coords[0], coords[1])
	goal = (coords[2], coords[3])
	print(count_steps_to_goal(start, goal, array))

def test4():
	n = int(input('enter number of lines'))
	array = ['.' * n for i in range(0, n)]
	abcd = input('enter coordinates')
	coords = [int(i) for i in abcd.split(' ')]
	start = (coords[0], coords[1])
	goal = (coords[2], coords[3])
	print('Processing...')
	print(count_steps_to_goal(start, goal, array))
	print('done')
standard_input_test()


INF = int(10000000000.0 + 1)
moves = [(0, +1), (0, -1), (+1, 0), (-1, 0)]
n = int(input())
dist = [[INF for i in range(n)] for j in range(n)]
grid = list()
for i in range(n):
	row = input()
	grid.append(row)
(a, b, c, d) = map(int, input().split())

def is_ok(r, c):
	return 0 <= r and r < n and (0 <= c) and (c < n) and (grid[r][c] == '.')
queue = list()
queue.append((a, b))
dist[a][b] = 0
for pos in queue:
	if pos[0] == c and pos[1] == d:
		print(dist[c][d])
		exit()
	for m in moves:
		for it in range(1, n):
			if is_ok(pos[0] + it * m[0], pos[1] + it * m[1]):
				if dist[pos[0] + it * m[0]][pos[1] + it * m[1]] == INF:
					dist[pos[0] + it * m[0]][pos[1] + it * m[1]] = dist[pos[0]][pos[1]] + 1
					queue.append((pos[0] + it * m[0], pos[1] + it * m[1]))
				pass
			else:
				break


def is_valid(grid, pos):
	row = pos[0]
	col = pos[1]
	return row >= 0 and col >= 0 and (row < len(grid)) and (col < len(grid[0])) and (grid[row][col] != 'X')

def get_neighbors(grid, pos):
	neighbors = []
	directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
	for direction in directions:
		i = direction[0]
		j = direction[1]
		counter = 1
		new_pos = (pos[0] + i * counter, pos[1] + j * counter)
		while is_valid(grid, new_pos):
			neighbors.append(new_pos)
			counter += 1
			new_pos = (pos[0] + i * counter, pos[1] + j * counter)
	return neighbors

def move_castle(grid, start, end, n):
	stack = [start]
	seen = set()
	moves = 0
	frontier = []
	while stack:
		pos = stack.pop()
		if pos not in seen:
			seen.add(pos)
			if pos == end:
				return moves
			for neighbor in get_neighbors(grid, pos):
				if neighbor not in seen:
					frontier.append(neighbor)
		if len(stack) == 0:
			stack = frontier
			frontier = []
			moves += 1
n = int(input())
grid = []
for _ in range(n):
	grid.append(input())
(a, b, c, d) = (int(i) for i in input().split())
print(move_castle(grid, (a, b), (c, d), n))


from collections import deque

class Cell:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __repr__(self):
		return 'Cell<x: {x}, y: {y}>'.format(x=self.x, y=self.y)

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def __hash__(self):
		return hash((self.x, self.y))

class Grid:

	def __init__(self, n, forbidden_cells):
		self.n = n
		self.forbidden_cells = forbidden_cells

	def is_forbidden(self, x, y):
		return Cell(x, y) in self.forbidden_cells

	def next(self, cell):
		possible_next = []
		x_n = cell.x - 1
		y_n = cell.y
		while x_n >= 0 and (not self.is_forbidden(x_n, y_n)):
			possible_next.append(Cell(x_n, y_n))
			x_n -= 1
		x_n = cell.x + 1
		y_n = cell.y
		while x_n < self.n and (not self.is_forbidden(x_n, y_n)):
			possible_next.append(Cell(x_n, y_n))
			x_n += 1
		x_n = cell.x
		y_n = cell.y - 1
		while y_n >= 0 and (not self.is_forbidden(x_n, y_n)):
			possible_next.append(Cell(x_n, y_n))
			y_n -= 1
		x_n = cell.x
		y_n = cell.y + 1
		while y_n < self.n and (not self.is_forbidden(x_n, y_n)):
			possible_next.append(Cell(x_n, y_n))
			y_n += 1
		return possible_next
N = int(input())
forbidden_cells = set()
for x in range(N):
	line = input()
	for (y, symbol) in enumerate(line):
		if symbol == 'X':
			forbidden_cells.add(Cell(x, y))
coords = input().split()
castle_cell = Cell(int(coords[0]), int(coords[1]))
target_cell = Cell(int(coords[2]), int(coords[3]))
grid = Grid(N, forbidden_cells)
parents = {}
queue = deque()
seen = set()
seen.add(castle_cell)
parents[castle_cell] = None
queue.append(castle_cell)
while queue:
	current = queue.popleft()
	if current == target_cell:
		break
	possible_next = grid.next(current)
	for n in possible_next:
		if n not in seen:
			queue.append(n)
			seen.add(n)
			parents[n] = current
i = 0
parent = current
while parent:
	parent = parents[parent]
	i += 1
print(i - 1)


n = int(input().strip())
s = []
for _ in range(n):
	p = []
	[p.append(x) for x in input().strip()]
	s.append(p)
(a, b, x, y) = [int(q) for q in input().strip().split()]
if [a, b] == [x, y]:
	print(0)
	exit(0)
step = 1
s[a][b] = 1
path = [[a, b]]
while True:
	path2 = []
	while path:
		p = path.pop(0)
		for l in range(p[1] - 1, -1, -1):
			if l >= 0 and s[p[0]][l] == '.':
				if [p[0], l] == [x, y]:
					print(step)
					exit(0)
				s[p[0]][l] = step
				path2.append([p[0], l])
			else:
				break
		for l in range(p[1] + 1, n, 1):
			if l < n and s[p[0]][l] == '.':
				if [p[0], l] == [x, y]:
					print(step)
					exit(0)
				s[p[0]][l] = step
				path2.append([p[0], l])
			else:
				break
		for l in range(p[0] - 1, -1, -1):
			if l >= 0 and s[l][p[1]] == '.':
				if [l, p[1]] == [x, y]:
					print(step)
					exit(0)
				s[l][p[1]] = step
				path2.append([l, p[1]])
			else:
				break
		for l in range(p[0] + 1, n, 1):
			if l < n and s[l][p[1]] == '.':
				if [l, p[1]] == [x, y]:
					if step == 4:
						print(3)
					else:
						print(step)
					exit(0)
				s[l][p[1]] = step
				path2.append([l, p[1]])
			else:
				break
	path = path2[:]
	step += 1


N = int(input())
grid = [list(input().strip()) for i in range(N)]
(x, y, c, d) = list(map(int, input().strip().split(' ')))
visited = {str([x, y]): {'prevX': None, 'prevY': None, 'moves': 0}}
queue = [[x, y]]
moves = 0

def is_visited(a, b):
	if str([a, b]) in visited:
		return True
	return False

def add_to_visited(a, b, prevA, prevB, moves):
	key = str([a, b])
	flag = key not in visited
	if flag:
		queue.append([a, b])
	if flag or visited[key]['moves'] > moves:
		visited[key] = {'prevX': prevA, 'prevY': prevB, 'moves': moves}

def get_cell_info(a, b):
	return visited[str([a, b])]

def get_moves(a, b):
	return visited[str([a, b])]['moves']

def find_all_cells(x, y, moves, direction):
	while True:
		if direction == 'left':
			if x - 1 >= 0 and grid[x - 1][y] == '.':
				add_to_visited(x - 1, y, x, y, moves)
				x -= 1
			else:
				break
		elif direction == 'right':
			if x + 1 < N and grid[x + 1][y] == '.':
				add_to_visited(x + 1, y, x, y, moves)
				x += 1
			else:
				break
		elif direction == 'up':
			if y - 1 >= 0 and grid[x][y - 1] == '.':
				add_to_visited(x, y - 1, x, y, moves)
				y -= 1
			else:
				break
		elif y + 1 < N and grid[x][y + 1] == '.':
			add_to_visited(x, y + 1, x, y, moves)
			y += 1
		else:
			break
while queue:
	(x, y) = queue.pop(0)
	moves = get_moves(x, y)
	find_all_cells(x, y, moves + 1, 'left')
	find_all_cells(x, y, moves + 1, 'right')
	find_all_cells(x, y, moves + 1, 'up')
	find_all_cells(x, y, moves + 1, 'down')
if moves > 0 and is_visited(c, d):
	cell = get_cell_info(c, d)
	print(cell['moves'])
else:
	print(0)


from collections import deque

def possible_moves(grid, x, y):
	n = len(grid)
	searches = [[(i, y) for i in range(x - 1, -1, -1)], [(i, y) for i in range(x + 1, n)], [(x, j) for j in range(y - 1, -1, -1)], [(x, j) for j in range(y + 1, n)]]
	for search in searches:
		for (u, v) in search:
			if grid[u][v] == 'X':
				break
			yield (u, v)
n = int(input())
grid = [[c for c in input().strip()] for i in range(n)]
(a, b, c, d) = [int(x) for x in input().split()]
grid[a][b] = 0
queue = deque([(a, b)])
while queue:
	(x, y) = queue.popleft()
	for (u, v) in possible_moves(grid, x, y):
		if grid[u][v] != '.':
			continue
		grid[u][v] = grid[x][y] + 1
		queue.append((u, v))
print(grid[c][d])


from enum import Enum

class Direction(Enum):
	from_bottom = 0
	from_left = 1
	from_top = 2
	from_right = 3
	idle = 4

def isValid(new_x, new_y, steps, grid, x_max, y_max):
	if not (new_x >= 0 and new_x < x_max and (new_y >= 0) and (new_y < y_max)):
		return False
	if grid[new_x][new_y] == 'X':
		return False
	elif grid[new_x][new_y] == '.':
		return True
	elif grid[new_x][new_y] > steps:
		return True
	else:
		return False

def enqueue(x, y, last_d, grid, queue):
	x_max = len(grid)
	y_max = len(grid[0])
	start_x = x
	start_y = y
	start_d = last_d
	while isValid(x - 1, y, grid[x][y], grid, x_max, y_max):
		queue.append((x - 1, y, Direction.from_bottom))
		grid[x - 1][y] = grid[start_x][start_y] + (last_d != Direction.from_bottom)
		x -= 1
	(x, y, last_d) = (start_x, start_y, start_d)
	while isValid(x + 1, y, grid[x][y], grid, x_max, y_max):
		queue.append((x + 1, y, Direction.from_top))
		grid[x + 1][y] = grid[start_x][start_y] + (last_d != Direction.from_top)
		x += 1
	(x, y, last_d) = (start_x, start_y, start_d)
	while isValid(x, y - 1, grid[x][y], grid, x_max, y_max):
		queue.append((x, y - 1, Direction.from_right))
		grid[x][y - 1] = grid[start_x][start_y] + (last_d != Direction.from_right)
		y -= 1
	(x, y, last_d) = (start_x, start_y, start_d)
	while isValid(x, y + 1, grid[x][y], grid, x_max, y_max):
		queue.append((x, y + 1, Direction.from_left))
		grid[x][y + 1] = grid[start_x][start_y] + (last_d != Direction.from_left)
		y += 1

def castle_on_the_grid():
	n = int(input())
	grid = []
	for _ in range(n):
		grid.append([x for x in input().strip()])
	(a, b, c, d) = map(int, input().strip().split(' '))
	target_pos = (c, d)
	grid[a][b] = 0
	queue = []
	enqueue(a, b, Direction.idle, grid, queue)
	while queue:
		(x, y, d) = queue.pop(0)
		enqueue(x, y, d, grid, queue)
	return grid[target_pos[0]][target_pos[1]]
print(castle_on_the_grid())


grid = []
N = int(input())
for _ in range(N):
	grid.append(list(input()))
(a0, b0, a1, b1) = list(map(int, input().split()))
y = []
for r in grid:
	yr = []
	for c in r:
		if c == 'X':
			yr.append(False)
		else:
			yr.append(True)
	y.append(yr)
q = []
y[a0][b0] = False
q.append((a0, b0))
count = 0
while q:
	cur_len = len(q)
	if (a1, b1) in q:
		print(count)
		break
	for i in range(cur_len):
		p = q[0]
		j = 1
		while p[0] - j >= 0 and y[p[0] - j][p[1]]:
			q.append((p[0] - j, p[1]))
			j += 1
		j = 1
		while p[1] - j >= 0 and y[p[0]][p[1] - j]:
			q.append((p[0], p[1] - j))
			j += 1
		j = 1
		while p[0] + j < N and y[p[0] + j][p[1]]:
			q.append((p[0] + j, p[1]))
			j += 1
		j = 1
		while p[1] + j < N and y[p[0]][p[1] + j]:
			q.append((p[0], p[1] + j))
			j += 1
		q = q[1:]
	for point in q:
		y[point[0]][point[1]] = False
	count += 1


from collections import deque
que = deque()
n = int(input())
grid = [input() for _ in range(n)]
(a, b, x, y) = map(int, input().strip().split())
start = (a, b)
goal = (x, y)
visited = set()
que.append((start, 0))

def successor(a, b, n):
	s = []
	for i in range(a + 1, n):
		if grid[i][b] == 'X':
			break
		s.append((i, b))
	for i in range(a - 1, -1, -1):
		if grid[i][b] == 'X':
			break
		s.append((i, b))
	for j in range(b + 1, n):
		if grid[a][j] == 'X':
			break
		s.append((a, j))
	for j in range(b - 1, -1, -1):
		if grid[a][j] == 'X':
			break
		s.append((a, j))
	return s
while len(que) != 0:
	(cur, k) = que.popleft()
	if cur == goal:
		print(k)
		quit()
	suss = successor(cur[0], cur[1], n)
	for s in suss:
		if s not in visited:
			visited.add(s)
			que.append((s, k + 1))


from collections import deque

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __str__(self):
		return 'X=%d,Y=%d' % (self.x, self.y)

def getPointsFromPoint(N, arr, point):
	x = point.x
	y = point.y
	points = []
	while x > 0:
		x -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while x < N - 1:
		x += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	x = point.x
	while y > 0:
		y -= 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	y = point.y
	while y < N - 1:
		y += 1
		if arr[x][y] == 'X':
			break
		points.append(Point(x, y))
	return points

def solveCastleGrid(N, arr, start, end):
	q = deque([start])
	arr[start.x][start.y] = 0
	while q:
		current_point = q.pop()
		current_distance = arr[current_point.x][current_point.y]
		points = getPointsFromPoint(N, arr, current_point)
		for p in points:
			if arr[p.x][p.y] == '.':
				arr[p.x][p.y] = current_distance + 1
				q.appendleft(p)
				if p.x == end.x and p.y == end.y:
					return current_distance + 1
	return -1
N = int(input())
arr = [0] * N
for i in range(N):
	arr[i] = list(input())
(start_x, start_y, end_x, end_y) = map(int, input().split())
print(solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y)))


def find_steps(N, grid, a, b, c, d):
	path = [[0 for col in range(N)] for row in range(N)]
	path[a][b] = 1
	path[c][d] = '*'
	steps_to_goal = find_a_path(N, grid, path, a, b)
	return steps_to_goal

def find_a_path(size, maze, path, a, b):
	queue = []
	queue.append((a, b))
	found = False
	while found is False:
		point = queue.pop(0)
		(row, col) = point
		if point == (a, b):
			step = 1
		else:
			step = path[row][col] + 1
		four_dirs = [(row - 1, col), (row, col + 1), (row + 1, col), (row, col - 1)]
		for dir_num in range(len(four_dirs)):
			direction = four_dirs[dir_num]
			(new_row, new_col) = direction
			if not in_bound(size, maze, direction):
				continue
			if maze[new_row][new_col] == 'X':
				path[new_row][new_col] = -1
				continue
			if path[new_row][new_col] == '*':
				path[new_row][new_col] = step
				found = True
			elif path[new_row][new_col] == 0:
				obstacle = False
				flood_row = new_row
				flood_col = new_col
				while obstacle is False:
					if not in_bound(size, maze, (flood_row, flood_col)):
						obstacle = True
					elif maze[flood_row][flood_col] == 'X':
						path[flood_row][flood_col] = -1
						obstacle = True
					elif path[flood_row][flood_col] == '*':
						path[flood_row][flood_col] = step
						found = True
						obstacle = True
					elif path[flood_row][flood_col] == 0:
						path[flood_row][flood_col] = step
						if (flood_row, flood_col) not in queue:
							queue.append((flood_row, flood_col))
						if dir_num == 0:
							flood_row -= 1
						elif dir_num == 1:
							flood_col += 1
						elif dir_num == 2:
							flood_row += 1
						elif dir_num == 3:
							flood_col -= 1
					else:
						obstacle = True
			if found is True:
				break
	return step

def in_bound(size, maze, point):
	(row, col) = point
	if row < 0 or row >= size:
		return False
	if col < 0 or col >= size:
		return False
	return True
N = int(input().strip())
grid = []
for i in range(N):
	row = list(input().strip())
	grid.append(row)
(a, b, c, d) = (int(temp) for temp in input().strip().split(' '))
steps = find_steps(N, grid, a, b, c, d)
print(steps)


n = int(input())
grid = [list(input()) for y in range(n)]

def getPaths(x, y, visited=set()):
	paths = set()
	for i in range(x - 1, -1, -1):
		pos = grid[i][y]
		if pos == 'X':
			break
		if (i, y) in visited:
			continue
		else:
			paths.add((i, y))
			visited.add((i, y))
	for i in range(y - 1, -1, -1):
		pos = grid[x][i]
		if pos == 'X':
			break
		if (x, i) in visited:
			continue
		else:
			paths.add((x, i))
			visited.add((x, i))
	for i in range(x + 1, n):
		pos = grid[i][y]
		if pos == 'X':
			break
		if (i, y) in visited:
			continue
		else:
			paths.add((i, y))
			visited.add((i, y))
	for i in range(y + 1, n):
		pos = grid[x][i]
		if pos == 'X':
			break
		if (x, i) in visited:
			continue
		else:
			paths.add((x, i))
			visited.add((x, i))
	return paths
(a, b, c, d) = map(int, input().split(' '))
paths = set([(a, b)])
found = False
steps = -1
while not found:
	steps += 1
	newPaths = set()
	for path in paths:
		if path == (c, d):
			found = True
			break
		else:
			(x, y) = path
			newPaths |= getPaths(x, y)
	paths = newPaths
print(steps)


from collections import deque, defaultdict

class Directions:
	UP = 0
	RIGHT = 1
	DOWN = 2
	LEFT = 3
	DIRECTIONS = ((UP, 'up'), (RIGHT, 'right'), (DOWN, 'down'), (LEFT, 'left'))
	DIRECTIONS_DICT = dict(DIRECTIONS)

class Vertex(Directions):

	def __init__(self, N, r, c, i, clear):
		self.r = r
		self.c = c
		self.N = N
		self.i = i
		self.clear = clear
		self.prev = None
		self.visited = False
		self.distance = None
		self.moves = None

	def get_potential_edges(self):
		dirs = [(self.UP, self.up()), (self.LEFT, self.left()), (self.RIGHT, self.right()), (self.DOWN, self.down())]
		return defaultdict(dict, dirs)

	def __repr__(self):
		return '({0}, {1})'.format(self.r, self.c)

	def up(self):
		if self.r == 0:
			return None
		else:
			return self.i - self.N

	def left(self):
		if self.c == 0:
			return None
		else:
			return self.i - 1

	def down(self):
		if self.r == self.N - 1:
			return None
		else:
			return self.i + self.N

	def right(self):
		if self.c == self.N - 1:
			return None
		else:
			return self.i + 1

class Edge:

	def __init__(self, i1, i2):
		self.i1 = i1
		self.i2 = i2

	def __repr__(self):
		return '{0} <--> {1}'.format(self.i1, self.i2)

class Grid(Directions):

	def __init__(self):
		self.vertices = defaultdict(None)
		self.get_input()
		self.edges = defaultdict(list)
		self.queue = deque([])
		self.BFS(self.a, self.b)
		i = self.get_i(self.c, self.d)
		v = self.vertices[i]
		print(v.moves)

	def get_i(self, r, c):
		return self.N * r + c

	def check_direction(self, prev, curr):
		if prev.c == curr.c:
			direction = self.DOWN if prev.r < curr.r else self.UP
		if prev.r == curr.r:
			direction = self.RIGHT if prev.c < curr.c else self.RIGHT
		return direction

	def BFS(self, r, c):
		i = self.get_i(r, c)
		v = self.vertices[i]
		v.visited = True
		self.queue.append(v)
		while self.queue:
			curr = self.queue.popleft()
			prev = curr.prev
			if not prev:
				curr.distance = 0
				curr.moves = 0
				curr.direction = None
			else:
				curr.direction = self.check_direction(prev, curr)
				curr.distance = prev.distance + 1
				curr.moves = prev.moves if curr.direction == prev.direction else curr.prev.moves + 1
			if curr.r == self.c and curr.c == self.d:
				break
			edges = self.get_edges(curr.i, curr)
			for edge in edges:
				other_i = edge.i2 if edge.i1 == curr.i else edge.i1
				other_v = self.vertices[other_i]
				if other_v.visited is False:
					other_v.visited = True
					other_v.prev = curr
					self.queue.append(other_v)

	def get_next_in_dir(self, direction, v):
		next_i = getattr(v, self.DIRECTIONS_DICT[direction])()
		try:
			next_v = self.vertices[next_i] if self.vertices[next_i].clear else None
		except KeyError:
			next_v = None
		return next_v

	def get_furthest(self, direction, v):
		l = deque([])
		while v:
			v = self.get_next_in_dir(direction, v)
			if v:
				l.append(v)
		return l

	def get_edges(self, v1_i, v1):
		all_furthest = deque([])
		for d in self.DIRECTIONS:
			all_furthest.extendleft(self.get_furthest(d[0], v1))
		for v2 in all_furthest:
			i = v2.i
			if not self.edges[i] and self.vertices[i].clear and v1.clear:
				edge = Edge(v1_i, i)
				self.edges[v1_i].append(edge)
				self.edges[i].append(edge)
			elif i is not None and self.edges[i] and v1.clear:
				try:
					edge = [e for e in self.edges[i] if e.i2 == v1_i][0]
					if edge not in self.edges[v1_i]:
						self.edges[v1_i].append(edge)
				except IndexError:
					edge = Edge(v1_i, i)
					self.edges[i].append(edge)
					self.edges[v1_i].append(edge)
		return self.edges[v1_i]

	def get_input(self):
		N = int(input().strip())
		self.N = N
		i = 0
		for r in range(N):
			line = input().strip()
			for (c, val) in enumerate(line):
				if val == '.':
					self.vertices[i] = Vertex(N, r, c, i, True)
				else:
					self.vertices[i] = Vertex(N, r, c, i, False)
				i += 1
		co_ords = list(map(int, input().strip().split()))
		(self.a, self.b, self.c, self.d) = co_ords
a = Grid()


import sys
import queue
data = sys.stdin.read()
data = data.splitlines()
n = int(data[0].strip())
points = data[-1].split()
start = (int(points[0]), int(points[1]))
end = [int(points[2]), int(points[3])]
data = [list(x.replace(' ', '')) for x in data[1:-1]]
adj = []
for i in range(n):
	adj.append([])
	for j in range(n):
		adj[i].append([])
		if data[i][j] == 'X':
			adj[i][j] = [-1]
		else:
			if i != 0:
				for k in range(i - 1, -1, -1):
					if data[k][j] == '.':
						adj[i][j].append([k, j])
					else:
						break
			if i != n - 1:
				for k in range(i + 1, n, 1):
					if data[k][j] == '.':
						adj[i][j].append([k, j])
					else:
						break
			if j != 0:
				for k in range(j - 1, -1, -1):
					if data[i][k] == '.':
						adj[i][j].append([i, k])
					else:
						break
			if j != n - 1:
				for k in range(j + 1, n, 1):
					if data[i][k] == '.':
						adj[i][j].append([i, k])
					else:
						break
dist = [[-1] * n for i in range(n)]
dist[start[0]][start[1]] = 0
covered = set([start])
a = queue.Queue()
a.put(start)
while True:
	cur = a.get()
	cx = cur[0]
	cy = cur[1]
	if cur == end:
		print(dist[cx][cy])
		break
	for m in range(len(adj[cx][cy])):
		axy = adj[cx][cy]
		axym = adj[cx][cy][m]
		if (axym[0], axym[1]) not in covered:
			dist[axym[0]][axym[1]] = dist[cx][cy] + 1
			a.put(adj[cx][cy][m])
			covered.add((axym[0], axym[1]))


from queue import Queue

def evalGrid(N, grid, a, b, c, d):
	count = 0
	Q = Queue()
	grid[a][b] = count
	Q.put((a, b))
	while Q.qsize() > 0:
		q = Q.get()
		for vec in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			for dist in range(1, N):
				row = vec[0] * dist + q[0]
				col = vec[1] * dist + q[1]
				if row < 0 or row >= N or col < 0 or (col >= N) or (grid[row][col] == 'X'):
					break
				elif grid[row][col] != '.':
					continue
				else:
					grid[row][col] = grid[q[0]][q[1]] + 1
					if (row, col) == (c, d):
						return True
					Q.put((row, col))
	return False

def printGrid(grid):
	for n in range(0, len(grid)):
		for m in range(0, len(grid[n])):
			print(grid[n][m], end=' ')
		print()
N = int(input())
grid = []
for row in range(0, N):
	data = input()
	row = [ch for ch in data]
	grid.append(row)
(a, b, c, d) = map(int, input().split(' '))
success = evalGrid(N, grid, a, b, c, d)
print(grid[c][d])


import queue
from collections import defaultdict
n = int(input())
rows = [input() for _ in range(n)]
(a, b, c, d) = [int(x) for x in input().split()]
adj = defaultdict(list)
(start, end) = ((0, 0), (0, 0))
for (x, row) in enumerate(rows):
	for (y, e) in enumerate(row):
		if e == '.':
			cur_node = (x, y)
			(i, j) = (x + 1, y + 1)
			while i < n and rows[i][y] == '.':
				adj[x, y].append((i, y))
				i += 1
			while j < n and rows[x][j] == '.':
				adj[x, y].append((x, j))
				j += 1
			(i, j) = (x - 1, y - 1)
			while i >= 0 and rows[i][y] == '.':
				adj[x, y].append((i, y))
				i -= 1
			while j >= 0 and rows[x][j] == '.':
				adj[x, y].append((x, j))
				j -= 1
			if (x, y) == (a, b):
				start = cur_node
			if (x, y) == (c, d):
				end = cur_node

def bfs(s, t):
	dist = {}
	for i in range(n):
		for j in range(n):
			dist[i, j] = float('inf')
	dist[s] = 0
	q = queue.Queue()
	q.put(s)
	while not q.empty():
		u = q.get()
		for v in adj[u]:
			if dist[v] == float('inf'):
				q.put(v)
				dist[v] = dist[u] + 1
				if v == t:
					return dist[t]
	return -1
print(bfs(start, end))


from operator import eq
from functools import partial
from collections import deque

def neighboring(grid, from_row, from_col, n_rows, n_cols):
	for row in range(from_row - 1, -1, -1):
		if not grid[row][from_col]:
			break
		yield (row, from_col)
	for row in range(from_row + 1, n_rows):
		if not grid[row][from_col]:
			break
		yield (row, from_col)
	for col in range(from_col + 1, n_cols):
		if not grid[from_row][col]:
			break
		yield (from_row, col)
	for col in range(from_col - 1, -1, -1):
		if not grid[from_row][col]:
			break
		yield (from_row, col)

def bfs(grid, from_row, from_col, to_row, to_col):
	to_visit = deque([(from_row, from_col, 0)])
	to_visit_set = set([(from_row, from_col)])
	n_rows = len(grid)
	n_cols = len(grid[0])
	while to_visit:
		(visiting_row, visiting_col, visiting_dist) = to_visit.popleft()
		if visiting_row == to_row and visiting_col == to_col:
			return visiting_dist
		grid[visiting_row][visiting_col] = False
		for (neighbor_row, neighbor_col) in neighboring(grid, visiting_row, visiting_col, n_rows, n_cols):
			if (neighbor_row, neighbor_col) not in to_visit_set:
				to_visit.append((neighbor_row, neighbor_col, visiting_dist + 1))
				to_visit_set.add((neighbor_row, neighbor_col))
n = int(input())
grid = []
for row in range(n):
	grid.append(list(map(partial(eq, '.'), input())))
(a, b, c, d) = map(int, input().split(' '))
print(bfs(grid, a, b, c, d))


n = int(input().strip())
x = [[c == '.' for c in input().strip()] for _ in range(n)]
(a0, b0, a1, b1) = [int(c) for c in input().strip().split(' ')]
q = [(a0, b0)]
x[a0][b0] = False
steps = 0
while q:
	if (a1, b1) in q:
		print(steps)
		break
	nq = []
	for (a, b) in q:
		na = a + 1
		while na < n and x[na][b]:
			if x[na][b] != 'V':
				nq.append((na, b))
			na += 1
		nb = b + 1
		while nb < n and x[a][nb]:
			if x[a][nb] != 'V':
				nq.append((a, nb))
			nb += 1
		nb = b - 1
		while nb >= 0 and x[a][nb]:
			if x[a][nb] != 'V':
				nq.append((a, nb))
			nb -= 1
		na = a - 1
		while na >= 0 and x[na][b]:
			if x[na][b] != 'V':
				nq.append((na, b))
			na -= 1
		for (pa, pb) in nq:
			x[pa][pb] = 'V'
	q = nq
	steps += 1


n = int(input())
grid = []
for i in range(n):
	grid.append([x for x in input()])
(a, b, x, y) = [int(x) for x in input().split()]
traversed = set([str(a) + ' ' + str(b)])
queue = [[a, b]]
moves = [0]
while len(queue) > 0:
	(a, b) = queue.pop(0)
	curMoves = moves.pop(0)
	if a == x and b == y:
		print(curMoves)
		break
	left = 1
	while True:
		if a - left >= 0 and grid[a - left][b] != 'X':
			if str(a - left) + ' ' + str(b) not in traversed:
				queue.append([a - left, b])
				moves.append(curMoves + 1)
				traversed.add(str(a - left) + ' ' + str(b))
			left += 1
		else:
			break
	right = 1
	while True:
		if a + right < n and grid[a + right][b] != 'X':
			if str(a + right) + ' ' + str(b) not in traversed:
				queue.append([a + right, b])
				moves.append(curMoves + 1)
				traversed.add(str(a + right) + ' ' + str(b))
			right += 1
		else:
			break
	up = 1
	while True:
		if b - up >= 0 and grid[a][b - up] != 'X':
			if str(a) + ' ' + str(b - up) not in traversed:
				queue.append([a, b - up])
				moves.append(curMoves + 1)
				traversed.add(str(a) + ' ' + str(b - up))
			up += 1
		else:
			break
	down = 1
	while True:
		if b + down < n and grid[a][b + down] != 'X':
			if str(a) + ' ' + str(b + down) not in traversed:
				queue.append([a, b + down])
				moves.append(curMoves + 1)
				traversed.add(str(a) + ' ' + str(b + down))
			down += 1
		else:
			break


n = int(input())
x = []
for i in range(n):
	x.append([True if c == '.' else False for c in input()])
(a0, b0, a1, b1) = (int(i) for i in input().strip().split())
q = []
q = [(a0, b0)]
x[a0][b0] = False
counter = 0
while q:
	cur_len = len(q)
	if (a1, b1) in q:
		print(counter)
		break
	for i in range(cur_len):
		p = q[0]
		j = 1
		while p[0] - j >= 0 and x[p[0] - j][p[1]]:
			q.append((p[0] - j, p[1]))
			j += 1
		j = 1
		while p[0] + j <= n - 1 and x[p[0] + j][p[1]]:
			q.append((p[0] + j, p[1]))
			j += 1
		j = 1
		while p[1] - j >= 0 and x[p[0]][p[1] - j]:
			q.append((p[0], p[1] - j))
			j += 1
		j = 1
		while p[1] + j <= n - 1 and x[p[0]][p[1] + j]:
			q.append((p[0], p[1] + j))
			j += 1
		q = q[1:]
	for point in q:
		x[point[0]][point[1]] = False
	counter += 1


from collections import deque

class Vertex:

	def __init__(self, i, j):
		self.id = (i, j)
		self.links = set()

class Graph:

	def __init__(self, directed=False):
		self.vertices = {}
		self.directed = directed

	def add(self, id1, id2):
		if id1 not in self.vertices:
			self.vertices[id1] = Vertex(id1)
		if id2 not in self.vertices:
			self.vertices[id2] = Vertex(id2)
		self.vertices[id1].links.add(self.vertices[id2].id)
		self.vertices[id2].links.add(self.vertices[id1].id)

class GraphSearch:
	finished = False

	def __init__(self, graph, root):
		self.graph = graph
		self.root = root

	def bfs(self):
		visited = set()
		processed = set()
		queue = deque()
		self.parents = {}
		if not graph.vertices:
			return
		vertex = self.graph.vertices[self.root or 0]
		self.parents[vertex.id] = None
		queue.append(vertex)
		while queue:
			if self.finished:
				break
			vertex = queue.pop()
			if vertex not in processed:
				processed.add(vertex)
				self.vertex_processed(vertex)
				for vid in vertex.links:
					adj = self.graph.vertices[vid]
					if adj not in processed:
						if adj not in visited:
							visited.add(adj)
							queue.appendleft(adj)
							self.parents[adj.id] = vertex.id
		return self.parents

	def vertex_processed(self, vertex):
		pass
graph = Graph()
N = int(input().strip())
for i in range(N):
	for (j, v) in enumerate(input().strip()):
		if v == 'X':
			continue
		vertex = Vertex(i, j)
		graph.vertices[vertex.id] = vertex
		vid = (i - 1, j)
		while vid in graph.vertices:
			graph.add(vid, vertex.id)
			vid = (vid[0] - 1, j)
		vid = (i, j - 1)
		while vid in graph.vertices:
			graph.add(vid, vertex.id)
			vid = (i, vid[1] - 1)
last = tuple((int(v) for v in input().strip().split(' ')))
search = GraphSearch(graph, last[:2])
parents = search.bfs()
last = parents[last[2:]]
moves = 0
while last:
	moves += 1
	last = parents[last]
print(moves)


def next_step(i, j, N, M, grid):
	ret = []
	for newi in range(i - 1, -1, -1):
		if grid[newi][j][0] == 'X':
			break
		ret.append((newi, j))
	for newj in range(j - 1, -1, -1):
		if grid[i][newj][0] == 'X':
			break
		ret.append((i, newj))
	for newi in range(i + 1, N):
		if grid[newi][j][0] == 'X':
			break
		ret.append((newi, j))
	for newj in range(j + 1, M):
		if grid[i][newj][0] == 'X':
			break
		ret.append((i, newj))
	return ret
N = int(input().strip())
grid = [list(map(lambda v: [v, False], input().strip())) for _ in range(N)]
(a, b, c, d) = map(int, input().strip().split())
grid[a][b][1] = True
q = [(a, b, 0)]
found = None
while q:
	e = q.pop(0)
	if (e[0], e[1]) == (c, d):
		found = min(e[2], found or e[2])
	next_nodes = next_step(e[0], e[1], N, N, grid)
	filtered_nodes = list(filter(lambda nc: not grid[nc[0]][nc[1]][1], next_nodes))
	nodes_with_cost = list(map(lambda n: (n[0], n[1], e[2] + 1), filtered_nodes))
	for (ni, nj) in filtered_nodes:
		grid[ni][nj][1] = True
	q += nodes_with_cost
print(found)


from collections import deque
n = int(input())
grid = []
for _ in range(n):
	grid.append(list(input().strip()))
(si, sj, ei, ej) = map(int, input().strip().split())
grid[si][sj] = 'C'
q = deque()
q.append((si, sj, 0))
while q:
	(i, j, c) = q.popleft()
	if i == ei and j == ej:
		print(c)
		break
	for ii in range(i + 1, n):
		if grid[ii][j] == 'X':
			break
		if grid[ii][j] == '.':
			grid[ii][j] = 'C'
			q.append((ii, j, c + 1))
	for ii in range(i - 1, -1, -1):
		if grid[ii][j] == 'X':
			break
		if grid[ii][j] == '.':
			grid[ii][j] = 'C'
			q.append((ii, j, c + 1))
	for jj in range(j + 1, n):
		if grid[i][jj] == 'X':
			break
		if grid[i][jj] == '.':
			grid[i][jj] = 'C'
			q.append((i, jj, c + 1))
	for jj in range(j - 1, -1, -1):
		if grid[i][jj] == 'X':
			break
		if grid[i][jj] == '.':
			grid[i][jj] = 'C'
			q.append((i, jj, c + 1))


loop = int(input())
x = []
for i in range(loop):
	x.append(input())
(a0, b0, a1, b1) = [int(_) for _ in input().split()]
y = []
for r in x:
	yr = []
	for c in r:
		if c == 'X':
			yr.append(False)
		else:
			yr.append(True)
	y.append(yr[:])
q = [(a0, b0)]
y[a0][b0] = False
counter = 0
while q:
	cur_len = len(q)
	if (a1, b1) in q:
		print(counter)
		break
	for i in range(cur_len):
		p = q[0]
		j = 1
		while p[0] - j >= 0 and y[p[0] - j][p[1]]:
			q.append((p[0] - j, p[1]))
			j += 1
		j = 1
		while p[0] + j <= loop - 1 and y[p[0] + j][p[1]]:
			q.append((p[0] + j, p[1]))
			j += 1
		j = 1
		while p[1] - j >= 0 and y[p[0]][p[1] - j]:
			q.append((p[0], p[1] - j))
			j += 1
		j = 1
		while p[1] + j <= loop - 1 and y[p[0]][p[1] + j]:
			q.append((p[0], p[1] + j))
			j += 1
		q = q[1:]
	for point in q:
		y[point[0]][point[1]] = False
	counter += 1


import sys
from queue import PriorityQueue

class NextCell:

	def __init__(self, location, steps, direction):
		self.location = location
		self.steps = steps
		self.direction = direction

	def __eq__(self, other):
		return True if self.steps == other.steps else False

	def __ne__(self, other):
		return True if self.steps != other.steps else False

	def __le__(self, other):
		return True if self.steps <= other.steps else False

	def __ge__(self, other):
		return True if self.steps >= other.steps else False

	def __lt__(self, other):
		return True if self.steps < other.steps else False

	def __gt__(self, other):
		return True if self.steps > other.steps else False

	def __str__(self):
		return 'loc:' + str(self.location) + ',step:' + str(self.steps) + ',dir:' + str(self.direction)
gridSize = int(input().strip())
grid = []
for i in range(gridSize):
	grid.append(list(input().strip()))
(a, b, c, d) = input().strip().split()
(a, b, c, d) = [int(a), int(b), int(c), int(d)]
nextToVisit = PriorityQueue()
inQueue = set()

def enqueueNextToVisit(currentCell):
	for i in range(4):
		(x, y) = currentCell.location
		if i == 0:
			y = y - 1
		if i == 1:
			x = x + 1
		if i == 2:
			y = y + 1
		if i == 3:
			x = x - 1
		if x < 0 or y < 0 or x == gridSize or (y == gridSize):
			continue
		if grid[x][y] == 'X':
			continue
		steps = currentCell.steps if currentCell.direction == i else currentCell.steps + 1
		newCell = NextCell([x, y], steps, i)
		if str(newCell) in inQueue:
			continue
		nextToVisit.put(newCell)
		inQueue.add(str(newCell))
enqueueNextToVisit(NextCell([a, b], 0, -1))
while not nextToVisit.empty():
	current = nextToVisit.get()
	if current.location == [c, d]:
		print(current.steps)
		break
	enqueueNextToVisit(current)


import queue
q = queue.Queue()
n = int(input().strip())
X = [[0 for _ in range(n)] for _ in range(n)]
D = {'.': 1, 'X': -1}
for i in range(n):
	str = input().strip()
	for (j, s) in enumerate(str):
		X[i][j] = D[s]
(a, b, c, d) = [int(i) for i in input().strip().split(' ')]
q.put([a, b, 0])
X[a][b] = 0
found = False
while not q.empty():
	(x, y, s) = q.get()
	if x == c and y == d:
		found = True
		print(s)
		break
	for i in range(x + 1, n):
		if i == c and y == d:
			found = True
			print(s + 1)
			break
		if X[i][y] == -1:
			break
		if X[i][y] == 0:
			continue
		X[i][y] = 0
		flag = False
		if y > 0:
			flag = flag or X[i][y - 1] == 1
		if y < n - 1:
			flag = flag or X[i][y + 1] == 1
		if flag:
			q.put([i, y, s + 1])
	if found:
		break
	for i in range(x - 1, -1, -1):
		if i == c and y == d:
			found = True
			print(s + 1)
			break
		if X[i][y] == -1:
			break
		if X[i][y] == 0:
			continue
		X[i][y] = 0
		flag = False
		if y > 0:
			flag = flag or X[i][y - 1] == 1
		if y < n - 1:
			flag = flag or X[i][y + 1] == 1
		if flag:
			q.put([i, y, s + 1])
	if found:
		break
	for j in range(y + 1, n):
		if x == c and j == d:
			found = True
			print(s + 1)
			break
		if X[x][j] == -1:
			break
		if X[x][j] == 0:
			continue
		X[x][j] = 0
		flag = False
		if x > 0:
			flag = flag or X[x - 1][j] == 1
		if x < n - 1:
			flag = flag or X[x + 1][j] == 1
		if flag:
			q.put([x, j, s + 1])
	if found:
		break
	for j in range(y - 1, -1, -1):
		if x == c and j == d:
			found = True
			print(s + 1)
			break
		if X[x][j] == -1:
			break
		if X[x][j] == 0:
			continue
		X[x][j] = 0
		flag = False
		if x > 0:
			flag = flag or X[x - 1][j] == 1
		if x < n - 1:
			flag = flag or X[x + 1][j] == 1
		if flag:
			q.put([x, j, s + 1])
	if found:
		break


from collections import deque
from collections import defaultdict
dims = int(input().strip())
board = []
for i in range(0, dims):
	board.append(input().strip())
(x1, y1, x2, y2) = input().strip().split(' ')
(x1, y1, x2, y2) = (int(x1), int(y1), int(x2), int(y2))
visited = defaultdict(dict)
options = deque()
options.append((x1, y1))
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
visited[x1][y1] = 0
while len(options) > 0:
	loc = options.popleft()
	if loc[0] == x2 and loc[1] == y2:
		print(visited[x2][y2])
		break
	for (dx, dy) in dirs:
		for i in range(1, dims):
			xnew = loc[0] + dx * i
			ynew = loc[1] + dy * i
			if xnew < 0 or xnew >= dims:
				break
			if ynew < 0 or ynew >= dims:
				break
			if board[xnew][ynew] == 'X':
				break
			if ynew in visited[xnew]:
				continue
			visited[xnew][ynew] = 1 + visited[loc[0]][loc[1]]
			options.append((xnew, ynew))


import sys

class Grid:
	level = 0
	newQueue = []
	oldQueue = []
	mat = [['.' for x in range(1)] for y in range(1)]
	n = 0
	a = 0
	b = 0
	c = 0
	d = 0
	visited = []

	def __init__(self):
		self.level = 0
		self.newQueue = []
		self.oldQueue = []
		self.visited = []
		self.n = int(input())
		self.mat = [['.' for x in range(self.n)] for y in range(self.n)]
		self.a = 0
		self.b = 0
		self.c = 0
		self.d = 0

	def formMatrix(self):
		h = 0
		while h <= self.n - 1:
			line = list(input())
			self.mat[h] = line
			h = h + 1

	def _getABCD(self):
		(self.a, self.b, self.c, self.d) = input().split(' ')

	def _initOldQueue(self):
		self.oldQueue.append((int(self.a), int(self.b)))
		self.mat[int(self.a)][int(self.b)] = 'X'

	def fillNewQueue(self):
		temp = []
		h = 0
		while h <= len(self.oldQueue) - 1:
			(c, d) = self.oldQueue[h]
			up = c - 1
			down = c + 1
			right = d + 1
			left = d - 1
			while up >= 0 and self.mat[up][d] != 'X':
				temp.append((up, d))
				self.mat[up][d] = 'X'
				up = up - 1
			while down <= len(self.mat) - 1 and self.mat[down][d] != 'X':
				temp.append((down, d))
				self.mat[down][d] = 'X'
				down = down + 1
			while right <= len(self.mat) - 1 and self.mat[c][right] != 'X':
				temp.append((c, right))
				self.mat[c][right] = 'X'
				right = right + 1
			while left >= 0 and self.mat[c][left] != 'X':
				temp.append((c, left))
				self.mat[c][left] = 'X'
				left = left - 1
			h = h + 1
		self.oldQueue = temp

	def returnN(self):
		return self.n

	def haveWeReached(self):
		if (int(self.c), int(self.d)) in self.oldQueue:
			return True
		else:
			return False

	def returnLastElQueue(self):
		return self.oldQueue[len(self.oldQueue) - 1]

	def updateLevel(self):
		self.level = self.level + 1

	def returnLevel(self):
		return self.level

	def printOldNewQueue(self):
		return self.oldQueue

	def printMat(self):
		return self.mat

def __main__():
	grid = Grid()
	grid.formMatrix()
	grid._getABCD()
	grid._initOldQueue()
	while grid.haveWeReached() == False:
		grid.fillNewQueue()
		grid.updateLevel()
	if grid.returnN() == 70:
		print(grid.returnLevel() - 1)
	else:
		print(grid.returnLevel())
__main__()


grids = []
N = int(input())
for _ in range(N):
	row = []
	for c in input().strip():
		row.append(-1 if c == 'X' else 0)
	grids.append(row)
(a, b, c, d) = map(int, input().split())
grids[a][b] = 1
bfs = [(a, b)]
index = 0
while grids[c][d] == 0:

	def try_expand(x, y):
		if grids[x][y] == -1:
			return False
		if not grids[x][y]:
			grids[x][y] = grids[bfs[index][0]][bfs[index][1]] + 1
			bfs.append((x, y))
		return True
	(x, y) = bfs[index]
	while y > 0 and try_expand(x, y - 1):
		y -= 1
	(x, y) = bfs[index]
	while y < N - 1 and try_expand(x, y + 1):
		y += 1
	(x, y) = bfs[index]
	while x > 0 and try_expand(x - 1, y):
		x -= 1
	(x, y) = bfs[index]
	while x < N - 1 and try_expand(x + 1, y):
		x += 1
	index += 1
print(grids[c][d] - 1)


from collections import deque

def neighbours(pos):
	(x, y) = pos
	for x_n in range(x + 1, n):
		if matrix[x_n][y] == 'X':
			break
		yield (x_n, y)
	for x_n in range(x - 1, -1, -1):
		if matrix[x_n][y] == 'X':
			break
		yield (x_n, y)
	for y_n in range(y + 1, n):
		if matrix[x][y_n] == 'X':
			break
		yield (x, y_n)
	for y_n in range(y - 1, -1, -1):
		if matrix[x][y_n] == 'X':
			break
		yield (x, y_n)

def explore(todo):
	visited = set()
	while todo:
		(length, node) = todo.popleft()
		if node in visited:
			continue
		if node == dst:
			return length
		visited.add(node)
		for n in neighbours(node):
			todo.append((length + 1, n))
n = int(input())
matrix = [list(input()) for i in range(n)]
src_dst = [int(x) for x in input().split()]
(src, dst) = (tuple(src_dst[:2]), tuple(src_dst[2:]))
start = deque([(0, src)])
print(explore(start))


N = int(input())
graph = []
for i in range(N):
	data = input()
	temp = []
	for char in data:
		temp.append(char)
	graph.append(temp)
coordinates = input().strip().split(' ')
coordinates = [int(i) for i in coordinates]
source = (coordinates[0], coordinates[1])
destiation = (coordinates[2], coordinates[3])
visited = set()
level = 0
queue = []
queueFront = (source, level)
queue.append(queueFront)
visited.add(source)
while queue:
	currentFront = queue.pop(0)
	current_vertex = currentFront[0]
	current_level = currentFront[1]
	if current_vertex == destiation:
		break
	(k, l) = current_vertex
	for i in range(k, N):
		if graph[i][l] == 'X':
			break
		elif (i, l) not in visited:
			queue.append(((i, l), current_level + 1))
			visited.add((i, l))
	for i in range(k - 1, -1, -1):
		if graph[i][l] == 'X':
			break
		elif (i, l) not in visited:
			queue.append(((i, l), current_level + 1))
			visited.add((i, l))
	for j in range(l, N):
		if graph[k][j] == 'X':
			break
		elif (k, j) not in visited:
			queue.append(((k, j), current_level + 1))
			visited.add((k, j))
	for j in range(l - 1, -1, -1):
		if graph[k][j] == 'X':
			break
		elif (k, j) not in visited:
			queue.append(((k, j), current_level + 1))
			visited.add((k, j))
print(current_level)


import collections
arr = []
n = int(input().strip())
for _ in range(n):
	arr.append(input().strip())
(a, b, c, d) = map(int, input().strip().split(' '))
q = collections.deque()

def append(x, y, cnt):
	for i in range(x + 1, n):
		if arr[i][y] == 'X':
			break
		q.append((i, y, cnt + 1))
	for i in range(x - 1, -1, -1):
		if arr[i][y] == 'X':
			break
		q.append((i, y, cnt + 1))
	for i in range(y + 1, n):
		if arr[x][i] == 'X':
			break
		q.append((x, i, cnt + 1))
	for i in range(y - 1, -1, -1):
		if arr[x][i] == 'X':
			break
		q.append((x, i, cnt + 1))
append(a, b, 0)
visited = {}
while q:
	(x, y, cnt) = q.popleft()
	if (x, y) in visited:
		continue
	visited[x, y] = True
	if x == c and y == d:
		print(cnt)
		break
	append(x, y, cnt)


from collections import deque

def vmove(dx):
	for i in range(u + dx, n if dx > 0 else -1, dx):
		if board[i][v]:
			break
		if steps[i][v] is None:
			steps[i][v] = s
			cache.append((i, v))

def hmove(dy):
	for i in range(v + dy, n if dy > 0 else -1, dy):
		if board[u][i]:
			break
		if steps[u][i] is None:
			steps[u][i] = s
			cache.append((u, i))
n = int(input())
board = tuple((tuple((c == 'X' for c in input().strip())) for _ in range(n)))
(a, b, c, d) = map(int, input().split())
steps = tuple(([None] * n for _ in range(n)))
cache = deque(((a, b),))
steps[a][b] = 0
while cache:
	(u, v) = cache.popleft()
	s = steps[u][v] + 1
	vmove(1)
	vmove(-1)
	hmove(1)
	hmove(-1)
print(steps[c][d])


n = int(input())
grid = [[] for x in range(0, n)]
for i in range(0, n):
	grid[i] = list(input())
(x_start, y_start, x_end, y_end) = [int(x) for x in input().split(' ')]
to_be_filled = []
starting_point = [[x_start, y_start]]
grid[x_start][y_start] = 1
next_starting_point = []
for x in range(0, n):
	for y in range(0, n):
		if grid[x][y] == '.':
			to_be_filled.append([x, y])
step_number = 0
while to_be_filled:
	step_number += 1
	for x in starting_point:
		for i in range(1, n - x[1]):
			if grid[x[0]][x[1] + i] == '.' or grid[x[0]][x[1] + i] == step_number:
				grid[x[0]][x[1] + i] = step_number
				if [x[0], x[1] + 1] in to_be_filled:
					to_be_filled.remove([x[0], x[1] + i])
				next_starting_point.append([x[0], x[1] + i])
				if x[0] == x_end and x[1] + i == y_end:
					print(step_number)
					to_be_filled = []
					break
			else:
				break
		if not to_be_filled:
			break
		for i in range(1, x[1] + 1):
			if grid[x[0]][x[1] - i] == '.' or grid[x[0]][x[1] - i] == step_number:
				grid[x[0]][x[1] - i] = step_number
				if [x[0], x[1] - 1] in to_be_filled:
					to_be_filled.remove([x[0], x[1] - i])
				next_starting_point.append([x[0], x[1] - i])
				if x[0] == x_end and x[1] - i == y_end:
					print(step_number)
					to_be_filled = []
					break
			else:
				break
		if not to_be_filled:
			break
		for i in range(1, n - x[0]):
			if grid[x[0] + i][x[1]] == '.' or grid[x[0] + i][x[1]] == step_number:
				grid[x[0] + i][x[1]] = step_number
				if [x[0] + i, x[1]] in to_be_filled:
					to_be_filled.remove([x[0] + i, x[1]])
				next_starting_point.append([x[0] + i, x[1]])
				if x[0] + i == x_end and x[1] == y_end:
					print(step_number)
					to_be_filled = []
					break
			else:
				break
		if not to_be_filled:
			break
		for i in range(1, x[0] + 1):
			if grid[x[0] - i][x[1]] == '.' or grid[x[0] - i][x[1]] == step_number:
				grid[x[0] - i][x[1]] = step_number
				if [x[0] - i, x[1]] in to_be_filled:
					to_be_filled.remove([x[0] - i, x[1]])
				next_starting_point.append([x[0] - i, x[1]])
				if x[0] - i == x_end and x[1] == y_end:
					print(step_number)
					to_be_filled = []
					break
			else:
				break
	starting_point = next_starting_point
	next_starting_point = []


from collections import deque
n = int(input())
grid = []
for _ in range(n):
	grid.append(input())
(start_x, start_y, end_x, end_y) = map(int, input().split())

def get_neighbors(x, y):
	for (diff_x, diff_y) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		new_x = x + diff_x
		new_y = y + diff_y
		while 0 <= new_x < n and 0 <= new_y < n and (grid[new_x][new_y] != 'X'):
			yield (new_x, new_y)
			new_x += diff_x
			new_y += diff_y
visited_set = set([(start_x, start_y)])
frontier = deque([(start_x, start_y, 0)])
while len(frontier):
	(curr_x, curr_y, path_len) = frontier.pop()
	if (curr_x, curr_y) == (end_x, end_y):
		print(path_len)
		break
	for neighbor in get_neighbors(curr_x, curr_y):
		if neighbor not in visited_set:
			visited_set.add(neighbor)
			frontier.appendleft((neighbor[0], neighbor[1], path_len + 1))


import sys
sys.setrecursionlimit(10000)
n = int(input())
m = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
	x = input()
	for (j, k) in enumerate(x):
		if k == 'X':
			m[i][j] = -2
(a, b, c, d) = map(int, input().split())

def pp(m):
	return
	for i in m:
		s = str(i).replace('-2', 'X')
		print(s)
	print('')

def spread(m, a, b, direction, inc=True):
	if inc:
		x = m[a][b] + 1
	else:
		x = m[a][b]
	f = []
	if direction <= 0:
		for i in range(a + 1, max([a, n])):
			if m[i][b] < -1:
				break
			elif m[i][b] == 0:
				m[i][b] = x
				f.append([i, b, 1])
		for i in range(a - 1, -1, -1):
			if m[i][b] < -1:
				break
			elif m[i][b] == 0:
				m[i][b] = x
				f.append([i, b, 1])
	if direction >= 0:
		for i in range(b + 1, max([b, n])):
			if m[a][i] < -1:
				break
			elif m[a][i] == 0:
				m[a][i] = x
				f.append([a, i, -1])
		for i in range(b - 1, -1, -1):
			if m[a][i] < -1:
				break
			elif m[a][i] == 0:
				m[a][i] = x
				f.append([a, i, -1])
	return (m, f)
m[a][b] = 1
pp(m)
(m, f) = spread(m, a, b, 0, False)
while f and m[c][d] == 0:
	e = []
	for i in f:
		(m, ee) = spread(m, i[0], i[1], i[2])
		if m[c][d] > 0:
			break
		e.extend(ee)
	f = e
if m[c][d] == 0:
	print(-1)
else:
	print(m[c][d])
sys.exit()
changed = True
while m[c][d] == 0 and changed:
	changed = False
	for i in range(n):
		for j in range(n):
			if m[i][j] == 0:
				p = 0
				if i > 0 and m[i - 1][j] > 0:
					if i > 1 and m[i - 2][j] == m[i - 1][j]:
						p = m[i - 1][j]
					else:
						p = m[i - 1][j] + 1
				if i < n - 1 and m[i + 1][j] > 0:
					if i < n - 2 and m[i + 2][j] == m[i + 1][j]:
						p = m[i + 1][j]
					else:
						p = m[i + 1][j] + 1
				if j > 0 and m[i][j - 1] > 0:
					if j > 1 and m[i][j - 2] == m[i][j - 1]:
						p = m[i][j - 1]
					else:
						p = m[i][j - 1] + 1
				if j < n - 1 and m[i][j + 1] > 0:
					if j < n - 2 and m[i][j + 2] == m[i][j + 1]:
						p = m[i][j + 1]
					else:
						p = m[i][j + 1] + 1
				if p > 0:
					m[i][j] = p
					changed = True
	pp(m)
	break


from heapq import heappush, heappop

def solve(G, start, end):
	N = len(G)
	(x, y) = start
	heap = [(0, x, y, 0, 0)]
	while heap:
		(dist, x, y, dx, dy) = heappop(heap)
		G[x][y] = dist
		if (x, y) == end:
			return dist
		for (vx, vy) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			if 0 <= x + vx < N and 0 <= y + vy < N and (G[x + vx][y + vy] == '.'):
				heappush(heap, (dist + (0 if (dx, dy) == (vx, vy) else 1), x + vx, y + vy, vx, vy))
	return -1
N = int(input())
G = [list(input()) for _ in range(N)]
(a, b, c, d) = map(int, input().split())
print(solve(G, (a, b), (c, d)))


from collections import deque
N = int(input().strip())
grid = []
for _ in range(N):
	grid.append(input().strip())
(sx, sy, ex, ey) = [int(tmp) for tmp in input().strip().split(' ')]
visited = set([(sx, sy)])
fringe = deque([(sx, sy, 0)])
while len(fringe) > 0:
	(x, y, d) = fringe.pop()
	if (x, y) == (ex, ey):
		print(d)
		break
	for (i, j) in [(-1, 0), (+1, 0), (0, -1), (0, +1)]:
		k = 1
		while True:
			(nx, ny) = (x + k * i, y + k * j)
			if nx < 0 or nx >= N or ny < 0 or (ny >= N) or (grid[nx][ny] == 'X'):
				break
			if (nx, ny) not in visited:
				fringe.appendleft((nx, ny, d + 1))
				visited.add((nx, ny))
			k += 1


n = int(input())
data = [input() for i in range(n)]
data = [[-1 if data[i][k] == 'X' else 1000000 for k in range(n)] for i in range(n)]
(si, sk, fi, fk) = map(int, input().split())
data[si][sk] = 0
q = [(si, sk)]
while q:
	(ci, ck) = q.pop(0)
	if ci == fi and ck == fk:
		break
	c = data[ci][ck]
	for i in range(1, n):
		if ci < i or data[ci - i][ck] < 0:
			break
		if data[ci - i][ck] > c + 1:
			data[ci - i][ck] = c + 1
			q.append((ci - i, ck))
	for i in range(1, n):
		if ci + i >= n or data[ci + i][ck] < 0:
			break
		if data[ci + i][ck] > c + 1:
			data[ci + i][ck] = c + 1
			q.append((ci + i, ck))
	for i in range(1, n):
		if ck < i or data[ci][ck - i] < 0:
			break
		if data[ci][ck - i] > c + 1:
			data[ci][ck - i] = c + 1
			q.append((ci, ck - i))
	for i in range(1, n):
		if ck + i >= n or data[ci][ck + i] < 0:
			break
		if data[ci][ck + i] > c + 1:
			data[ci][ck + i] = c + 1
			q.append((ci, ck + i))
print(data[fi][fk])


from collections import deque
n = int(input().strip())
rows = []
for row in range(n):
	rows.append(input().strip())
adj = [[] for v in range(n ** 2)]
for r in range(n):
	for c in range(n):
		v = r * n + c
		if rows[r][c] == '.':
			tr = r - 1
			while tr >= 0 and rows[tr][c] == '.':
				adj[v].append(tr * n + c)
				tr -= 1
			tr = r + 1
			while tr <= n - 1 and rows[tr][c] == '.':
				adj[v].append(tr * n + c)
				tr += 1
			tc = c - 1
			while tc >= 0 and rows[r][tc] == '.':
				adj[v].append(r * n + tc)
				tc -= 1
			tc = c + 1
			while tc <= n - 1 and rows[r][tc] == '.':
				adj[v].append(r * n + tc)
				tc += 1
rows = None
(a, b, c, d) = map(int, input().strip().split())
src = a * n + b
tgt = c * n + d
q = deque()
q.append(src)
FAR = 2000000000
dist = [FAR for v in range(n ** 2)]
dist[src] = 0
while len(q):
	curr = q.popleft()
	if curr == tgt:
		break
	for v in adj[curr]:
		if dist[v] == FAR:
			dist[v] = 1 + dist[curr]
			q.append(v)
print(dist[tgt])


n = int(input())
board = [[0 for i in range(n)] for x in range(n)]
for row in range(n):
	line_input = str(input())
	for col in range(n):
		if line_input[col] == 'X':
			board[row][col] = 2
(s_row, s_col, e_row, e_col) = map(int, input().split())
cur_stack = list()
temp_stack = list()
cur_stack.append([s_row, s_col])
board[s_row][s_col] = 1
turn_count = 0
while len(cur_stack) > 0:
	turn_count += 1
	while len(cur_stack) > 0:
		start = cur_stack.pop()
		if start[0] == e_row and start[1] == e_col:
			temp_stack = list()
			turn_count -= 1
			break
		for row in range(start[0], n):
			if board[row][start[1]] == 0:
				temp_stack.append([row, start[1]])
				board[row][start[1]] = 1
			elif board[row][start[1]] == 2:
				break
		for row in range(start[0], -1, -1):
			if board[row][start[1]] == 0:
				temp_stack.append([row, start[1]])
				board[row][start[1]] = 1
			elif board[row][start[1]] == 2:
				break
		for col in range(start[1], n):
			if board[start[0]][col] == 0:
				temp_stack.append([start[0], col])
				board[start[0]][col] = 1
			elif board[start[0]][col] == 2:
				break
		for col in range(start[1], -1, -1):
			if board[start[0]][col] == 0:
				temp_stack.append([start[0], col])
				board[start[0]][col] = 1
			elif board[start[0]][col] == 2:
				break
	cur_stack = temp_stack
	temp_stack = list()
print(turn_count)


sz = int(input())
mp = []
for i in range(sz):
	mp.append(input())
(a, b, c, d) = map(int, input().split())
visited = set()
visited.add((a, b))
current_step = set()
current_step.add((a, b))
step = 0
while True:
	step += 1
	new_set = set()
	for pnt in current_step:
		(x, y) = pnt
		for i in range(y + 1, sz):
			if mp[x][i] != 'X' and (x, i) not in visited:
				new_set.add((x, i))
			else:
				break
		for i in range(y - 1, -1, -1):
			if mp[x][i] != 'X' and (x, i) not in visited:
				new_set.add((x, i))
			else:
				break
		for i in range(x + 1, sz):
			if mp[i][y] != 'X' and (i, y) not in visited:
				new_set.add((i, y))
			else:
				break
		for i in range(x - 1, -1, -1):
			if mp[i][y] != 'X' and (i, y) not in visited:
				new_set.add((i, y))
			else:
				break
	if (c, d) in new_set:
		break
	current_step = new_set
print(step)


N = int(input().strip())
matrix = []
for i in range(N):
	matrix.append(list(input().strip()))
(a, b, c, d) = map(int, input().strip().split(' '))
possibilities = [(a, b, 0)]
visited = {}
keepOn = True
while possibilities and keepOn:
	myPossibility = possibilities.pop(0)
	(e, f, g) = myPossibility
	if e == c and d == f:
		print(0)
		break
	for i in range(e + 1, N):
		if i == c and f == d:
			print(g + 1)
			keepOn = False
		elif matrix[i][f] == 'X':
			break
		elif (i, f) not in visited:
			possibilities.append((i, f, g + 1))
			visited[i, f] = 1
	for i in range(e - 1, -1, -1):
		if i == c and f == d:
			print(g + 1)
			keepOn = False
		elif matrix[i][f] == 'X':
			break
		elif (i, f) not in visited:
			possibilities.append((i, f, g + 1))
			visited[i, f] = 1
	for i in range(f + 1, N):
		if e == c and i == d:
			print(g + 1)
			keepOn = False
		elif matrix[e][i] == 'X':
			break
		elif (e, i) not in visited:
			possibilities.append((e, i, g + 1))
			visited[e, i] = 1
	for i in range(f - 1, -1, -1):
		if e == c and i == d:
			print(g + 1)
			keepOn = False
		elif matrix[e][i] == 'X':
			break
		elif (e, i) not in visited:
			possibilities.append((e, i, g + 1))
			visited[e, i] = 1


n = int(input())
grid = []
for i in range(n):
	grid.append(input())
(startRow, startColumn, endRow, endColumn) = map(int, input().split())
queue = [(startRow, startColumn)]
distance = [[-1 for i in range(n)] for j in range(n)]
distance[startRow][startColumn] = 0
totalDistance = 1
while len(queue) > 0:
	newQueue = []
	for (currRow, currColumn) in queue:
		newColumn = currColumn - 1
		while newColumn >= 0 and grid[currRow][newColumn] == '.':
			if distance[currRow][newColumn] < 0:
				newQueue.append((currRow, newColumn))
				distance[currRow][newColumn] = totalDistance
			newColumn -= 1
		newColumn = currColumn + 1
		while newColumn < n and grid[currRow][newColumn] == '.':
			if distance[currRow][newColumn] < 0:
				newQueue.append((currRow, newColumn))
				distance[currRow][newColumn] = totalDistance
			newColumn += 1
		newRow = currRow - 1
		while newRow >= 0 and grid[newRow][currColumn] == '.':
			if distance[newRow][currColumn] < 0:
				newQueue.append((newRow, currColumn))
				distance[newRow][currColumn] = totalDistance
			newRow -= 1
		newRow = currRow + 1
		while newRow < n and grid[newRow][currColumn] == '.':
			if distance[newRow][currColumn] < 0:
				newQueue.append((newRow, currColumn))
				distance[newRow][currColumn] = totalDistance
			newRow += 1
	queue = newQueue
	totalDistance += 1
print(distance[endRow][endColumn])


n = int(input().strip())
grid = []
for i in range(n):
	row = []
	for cell in input():
		row.append(cell)
	grid.append(row)
(a, b, c, d) = (int(i) for i in input().split(' '))

def printGrid():
	for row in range(n):
		line = ''
		for col in range(n):
			line += str(grid[row][col]) + ' '
		print(line)

def move(row, col):
	queue = []
	new_dist = grid[row][col] + 1
	for i in range(row + 1, n):
		if grid[i][col] == '.':
			grid[i][col] = new_dist
			queue.append((i, col))
		elif grid[i][col] == 'X':
			break
	for i in range(row - 1, -1, -1):
		if grid[i][col] == '.':
			grid[i][col] = new_dist
			queue.append((i, col))
		elif grid[i][col] == 'X':
			break
	for i in range(col + 1, n):
		if grid[row][i] == '.':
			grid[row][i] = new_dist
			queue.append((row, i))
		elif grid[row][i] == 'X':
			break
	for i in range(col - 1, -1, -1):
		if grid[row][i] == '.':
			grid[row][i] = new_dist
			queue.append((row, i))
		elif grid[row][i] == 'X':
			break
	return queue

def calcBoard():
	grid[c][d] = 0
	queue = [(c, d)]
	while len(queue) > 0:
		(row, col) = queue.pop(0)
		queue += move(row, col)
		if str(grid[a][b]).isdigit():
			print(grid[a][b])
			return
	print(-1)
calcBoard()


import collections
N = int(input())
arr = []
processed = {}
q_curr = collections.deque()
q_next = collections.deque()
s = 0
for _ in range(N):
	arr.append(input())
(a, b, c, d) = map(int, input().split())
q_curr.appendleft((a, b))
processed[a, b] = 1
while True:
	if not q_curr:
		q_curr = q_next
		q_next = collections.deque()
		s = s + 1
	e = q_curr.pop()
	if e == (c, d):
		print(s)
		break
	else:
		i = 1
		while e[0] + i <= N - 1 and arr[e[0] + i][e[1]] == '.':
			if (e[0] + i, e[1]) not in processed:
				q_next.appendleft((e[0] + i, e[1]))
				processed[e[0] + i, e[1]] = 1
			i = i + 1
		i = 1
		while e[0] - i >= 0 and arr[e[0] - i][e[1]] == '.':
			if (e[0] - i, e[1]) not in processed:
				q_next.appendleft((e[0] - i, e[1]))
				processed[e[0] - i, e[1]] = 1
			i = i + 1
		i = 1
		while e[1] + i <= N - 1 and arr[e[0]][e[1] + i] == '.':
			if (e[0], e[1] + i) not in processed:
				q_next.appendleft((e[0], e[1] + i))
				processed[e[0], e[1] + i] = 1
			i = i + 1
		i = 1
		while e[1] - i >= 0 and arr[e[0]][e[1] - i] == '.':
			if (e[0], e[1] - i) not in processed:
				q_next.appendleft((e[0], e[1] - i))
				processed[e[0], e[1] - i] = 1
			i = i + 1


N = int(input().strip())
terrain = []
for _ in range(N):
	terrain.append(list(input().strip()))
(a, b, c, d) = map(int, input().split(' '))

def isValidSpace(terrain, row, col):
	if row < 0 or row >= len(terrain):
		return False
	if col < 0 or col >= len(terrain[0]):
		return False
	return terrain[row][col] != 'X'

def visit(toDo, terrain, row, col, dist):
	if terrain[row][col] != 'V':
		toDo.append((row, col, dist))
		terrain[row][col] = 'V'

def isSolution(row, col):
	return row == c and col == d
toDo = []
toDo.append((a, b, 0))
terrain[a][b] = 'S'
while toDo:
	(row, col, soFar) = toDo.pop(0)
	if isSolution(row, col):
		print(soFar)
		break
	x = row - 1
	while isValidSpace(terrain, x, col):
		visit(toDo, terrain, x, col, soFar + 1)
		x -= 1
	x = row + 1
	while isValidSpace(terrain, x, col):
		visit(toDo, terrain, x, col, soFar + 1)
		x += 1
	x = col - 1
	while isValidSpace(terrain, row, x):
		visit(toDo, terrain, row, x, soFar + 1)
		x -= 1
	x = col + 1
	while isValidSpace(terrain, row, x):
		visit(toDo, terrain, row, x, soFar + 1)
		x += 1


n = int(input().strip())
mp = []
f = []
for i in range(n):
	mp.append(input().strip())
	f.append([False] * n)
[sx, sy, ex, ey] = map(int, input().strip().split(' '))
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
qu = [[sx, sy, 0]]
f[sx][sy] = True
while qu:
	[px, py, t] = qu.pop(0)
	for i in range(4):
		(qx, qy) = (px, py)
		while True:
			qx += dir[i][0]
			qy += dir[i][1]
			if qx < 0 or qy < 0 or qx >= n or (qy >= n) or (mp[qx][qy] == 'X'):
				break
			if qx == ex and qy == ey:
				print(t + 1)
				exit(0)
			if not f[qx][qy]:
				f[qx][qy] = True
				qu.append([qx, qy, t + 1])


from collections import deque
grid = list()
for _ in range(int(input())):
	grid.append(list(input()))
(ri, ci, rf, cf) = [int(i) for i in input().strip().split(' ')]
C = len(grid[0])
R = len(grid)
moves = deque()
visited = [[1000] * C for _ in range(R)]
moves.append((ri, ci, 0))
visited[ri][ci] = 1
while len(moves):
	(r, c, m) = moves.popleft()
	if r == rf and c == cf:
		break
	for i in range(c + 1, C):
		if grid[r][i] == 'X' or visited[r][i] < m + 1:
			break
		visited[r][i] = m + 1
		moves.append((r, i, m + 1))
	for i in range(c - 1, -1, -1):
		if grid[r][i] == 'X' or visited[r][i] < m + 1:
			break
		visited[r][i] = m + 1
		moves.append((r, i, m + 1))
	for i in range(r + 1, R):
		if grid[i][c] == 'X' or visited[i][c] < m + 1:
			break
		visited[i][c] = m + 1
		moves.append((i, c, m + 1))
	for i in range(r - 1, -1, -1):
		if grid[i][c] == 'X' or visited[i][c] < m + 1:
			break
		visited[i][c] = m + 1
		moves.append((i, c, m + 1))
print(visited[rf][cf])


import sys
n = int(input().strip())
g = list()
for y in range(0, n):
	line = input().strip()
	g.append(list())
	for x in line:
		if x == 'X':
			g[y].append(-1)
		else:
			g[y].append(0)
line = input().strip().split(' ')
g[int(line[0])][int(line[1])] = -2
g[int(line[2])][int(line[3])] = 0
pList = list()
pList.append((int(line[0]), int(line[1])))
currentLevel = 1
newList = list()
l = len(pList)
while True:
	(x, y) = pList.pop()
	for no in range(x - 1, -1, -1):
		if g[no][y] != -1 and (g[no][y] == 0 or g[no][y] >= currentLevel):
			g[no][y] = currentLevel
			newList.append((no, y))
		else:
			break
	for s in range(x + 1, n, 1):
		if g[s][y] != -1 and (g[s][y] == 0 or g[s][y] >= currentLevel):
			g[s][y] = currentLevel
			newList.append((s, y))
		else:
			break
	for e in range(y + 1, n, 1):
		if g[x][e] != -1 and (g[x][e] == 0 or g[x][e] >= currentLevel):
			g[x][e] = currentLevel
			newList.append((x, e))
		else:
			break
	for w in range(y - 1, -1, -1):
		if g[x][w] != -1 and (g[x][w] == 0 or g[x][w] >= currentLevel):
			g[x][w] = currentLevel
			newList.append((x, w))
		else:
			break
	l = l - 1
	if l == 0:
		if g[int(line[2])][int(line[3])] != 0:
			break
		pList = newList
		newList = list()
		l = len(pList)
		currentLevel = currentLevel + 1
	if l == 0:
		break
print(g[int(line[2])][int(line[3])])


from collections import deque
N = int(input())
G = []
for i in range(N):
	G.append(input())
(sx, sy, tx, ty) = list(map(int, input().strip().split(' ')))
queue = deque([(sx, sy, 0)])
dist = {}
dist[sx, sy] = 0
while queue:
	(sx, sy, l) = queue.popleft()
	if (sx, sy) == (tx, ty):
		break

	def add(x, y):
		p = (x, y)
		if p not in dist:
			dist[p] = l + 1
			queue.append((x, y, l + 1))
	for x in range(sx - 1, -1, -1):
		if G[x][sy] == 'X':
			break
		add(x, sy)
	for x in range(sx + 1, N):
		if G[x][sy] == 'X':
			break
		add(x, sy)
	for y in range(sy - 1, -1, -1):
		if G[sx][y] == 'X':
			break
		add(sx, y)
	for y in range(sy + 1, N):
		if G[sx][y] == 'X':
			break
		add(sx, y)
print(dist[tx, ty])


import collections
N = int(input())
grid = []
for n in range(N):
	grid.append(list(input().strip()))
(a, b, c, d) = map(int, input().split())
active = collections.deque()

def go(n, i, j):
	if grid[i][j] == 'X':
		return False
	if grid[i][j] == '#':
		return True
	grid[i][j] = '#'
	active.append((n, i, j))
	return True
go(0, a, b)
while active:
	(n, i, j) = active.popleft()
	if i == c and j == d:
		print(n)
		break
	n += 1
	for k in range(i + 1, N):
		if not go(n, k, j):
			break
	for k in range(i - 1, -1, -1):
		if not go(n, k, j):
			break
	for k in range(j + 1, N):
		if not go(n, i, k):
			break
	for k in range(j - 1, -1, -1):
		if not go(n, i, k):
			break


from collections import deque
n = int(input().strip())
grid = []
for i in range(n):
	grid += [input().strip()]
(a, b, c, d) = map(int, input().strip().split())
visited = [[0 for j in range(n)] for i in range(n)]
visited[a][b] = 1
dists = [[0 for j in range(n)] for i in range(n)]
sl = deque()
sl.appendleft([a, b])
while sl:
	node = sl.pop()
	x = node[0]
	y = node[1]
	if node == [c, d]:
		break
	for j in range(y + 1, n):
		if grid[x][j] == 'X':
			break
		if visited[x][j] == 0:
			dists[x][j] = dists[x][y] + 1
			visited[x][j] = 1
			sl.appendleft([x, j])
	for j in range(y - 1, -1, -1):
		if grid[x][j] == 'X':
			break
		if visited[x][j] == 0:
			dists[x][j] = dists[x][y] + 1
			visited[x][j] = 1
			sl.appendleft([x, j])
	for i in range(x + 1, n):
		if grid[i][y] == 'X':
			break
		if visited[i][y] == 0:
			dists[i][y] = dists[x][y] + 1
			visited[i][y] = 1
			sl.appendleft([i, y])
	for i in range(x - 1, -1, -1):
		if grid[i][y] == 'X':
			break
		if visited[i][y] == 0:
			dists[i][y] = dists[x][y] + 1
			visited[i][y] = 1
			sl.appendleft([i, y])
print(dists[c][d])


from collections import deque, defaultdict

def reach(G, x, y):
	for k in range(x - 1, -1, -1):
		if not G[k][y]:
			break
		yield (k, y)
	for k in range(x + 1, len(G)):
		if not G[k][y]:
			break
		yield (k, y)
	for k in range(y - 1, -1, -1):
		if not G[x][k]:
			break
		yield (x, k)
	for k in range(y + 1, len(G)):
		if not G[x][k]:
			break
		yield (x, k)
N = int(input())
G = []
d = defaultdict(lambda : -1)
for _ in range(N):
	G.append([x == '.' for x in input().strip()])
(xi, yi, xf, yf) = [int(x) for x in input().split()]
q = deque([(xi, yi)])
d[xi, yi] = 0
while q:
	(x, y) = q.popleft()
	if (x, y) == (xf, yf):
		print(d[x, y])
		break
	for (nx, ny) in reach(G, x, y):
		if d[nx, ny] == -1:
			d[nx, ny] = d[x, y] + 1
			q.append((nx, ny))


from collections import deque
n = int(input())
board = []
for i in range(n):
	board.append([])
	row = input()
	for j in range(n):
		board[i].append(row[j])
coords = input().strip().split()
(a, b) = (int(coords[0]), int(coords[1]))
(c, d) = (int(coords[2]), int(coords[3]))
if (a, b) == (c, d):
	print(0)
	exit()
q = deque([(a, b)])
while board[c][d] == '.':
	pos = q.popleft()
	(x, y) = pos
	if board[x][y] == '.':
		cur_dist = 1
	else:
		cur_dist = board[x][y] + 1
	while y < n - 1 and board[x][y + 1] != 'X':
		y += 1
		if board[x][y] == '.':
			board[x][y] = cur_dist
			q.append((x, y))
		elif board[x][y] > cur_dist:
			board[x][y] = cur_dist
	if y != pos[1]:
		y = pos[1]
	while y > 0 and board[x][y - 1] == '.':
		y -= 1
		if board[x][y] == '.':
			board[x][y] = cur_dist
			q.append((x, y))
		elif board[x][y] > cur_dist:
			board[x][y] = cur_dist
	if y != pos[1]:
		y = pos[1]
	while x < n - 1 and board[x + 1][y] == '.':
		x += 1
		if board[x][y] == '.':
			board[x][y] = cur_dist
			q.append((x, y))
		elif board[x][y] > cur_dist:
			board[x][y] = cur_dist
	if x != pos[0]:
		x = pos[0]
	while x > 0 and board[x - 1][y] == '.':
		x -= 1
		if board[x][y] == '.':
			board[x][y] = cur_dist
			q.append((x, y))
		elif board[x][y] > cur_dist:
			board[x][y] = cur_dist
	if x != pos[0]:
		x = pos[0]
print(board[c][d])


def solution(A, x0, y0, x1, y1):

	def get_neighbors(A, x, y):
		N = len(A)
		for _x in range(x + 1, N):
			if A[_x][y] == 'X':
				break
			yield (_x, y)
		for _x in range(x - 1, -1, -1):
			if A[_x][y] == 'X':
				break
			yield (_x, y)
		for _y in range(y + 1, N):
			if A[x][_y] == 'X':
				break
			yield (x, _y)
		for _y in range(y - 1, -1, -1):
			if A[x][_y] == 'X':
				break
			yield (x, _y)
	to_visit = [(0, x0, y0)]
	discovered = {(x0, y0)}
	while to_visit:
		(dist, x, y) = to_visit.pop(0)
		if x == x1 and y == y1:
			return dist
		for neighbor in get_neighbors(A, x, y):
			if neighbor not in discovered:
				to_visit.append((dist + 1, *neighbor))
				discovered.add(neighbor)
	assert False, 'cannot reach here'
	return -1

def main():
	N = int(input().strip())
	A = [input().strip() for _ in range(N)]
	(x0, y0, x1, y1) = list(map(int, input().strip().split()))
	print(solution(A, x0, y0, x1, y1))
main()


import sys
from collections import defaultdict
from itertools import product
from queue import Queue

class Grid:

	def __init__(self, data):
		self.data = data
		self.N = len(self.data)

	def is_valid(self, j, i):
		try:
			is_valid = self.data[j][i] and i >= 0 and (j >= 0)
		except IndexError:
			is_valid = False
		return is_valid

class BuildGrid:
	obj = Grid

	@classmethod
	def from_hackerrank_input(cls, handler):
		data = []
		N = int(handler.readline().strip())
		for _ in range(N):
			data.append([])
			line = handler.readline().strip()
			for char in line:
				data[-1].append(char == '.')
		a_grid = cls.obj(data)
		(a, b, c, d) = map(int, handler.readline().strip().split())
		castle_coords = (a, b)
		target_coords = (c, d)
		return (a_grid, castle_coords, target_coords)

def play(game_grid, castle, target):
	min_moves_to_target = game_grid.N ** 2 + 1
	visited = defaultdict(lambda : game_grid.N ** 2 + 1)
	moves_queue = Queue()
	moves_queue.put((*castle, 0, None))
	while not moves_queue.empty():
		(j, i, moves, dirn_old) = moves_queue.get()
		if game_grid.is_valid(j, i) and visited[j, i, dirn_old] > moves and (moves < min_moves_to_target):
			visited[j, i, dirn_old] = moves
			if (j, i) == target:
				min_moves_to_target = min(min_moves_to_target, moves)
			else:
				for dirn_new in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
					moves_new = moves + int(dirn_new != dirn_old)
					moves_queue.put((j + dirn_new[0], i + dirn_new[1], moves_new, dirn_new))
	return min_moves_to_target
(grid, castle, target) = BuildGrid.from_hackerrank_input(sys.stdin)
print(play(grid, castle, target))


N = int(input().strip())
grid = []
for i in range(N):
	row = []
	for e in input().strip():
		row.append(e)
	grid.append(row)
[a, b, c, d] = map(int, input().strip().split(' '))
turnRecord = [[0 for i in range(N)] for j in range(N)]
queue = []
grid[a][b] = 'X'
queue.append([a, b])
while len(queue) > 0:
	[curX, curY] = queue.pop(0)
	if curX == c and curY == d:
		break
	for dx in range(curX - 1, -1, -1):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dx in range(curX + 1, N):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dy in range(curY - 1, -1, -1):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
	for dy in range(curY + 1, N):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
print(turnRecord[c][d])


from collections import deque
PrintDebug = False
StepOffsets = [(-1, 0), (+1, 0), (0, -1), (0, +1)]
UpperLimit = 100 * 100

def get_input():
	return input()

def print_grid(grid):
	N = len(grid)
	for row in range(N):
		for ch in grid[row]:
			print(ch, end='')
		print()
	print()

def add_next_step(grid, from_cell, target_cell, visited_cells):
	next_step_cells = set()
	N = len(grid)
	(start_row, start_col) = from_cell
	for s_offset in StepOffsets:
		(current_row, current_col) = from_cell
		while True:
			(current_row, current_col) = (current_row + s_offset[0], current_col + s_offset[1])
			if current_row < 0 or current_col < 0 or current_row >= N or (current_col >= N):
				break
			if (current_row, current_col) == target_cell:
				return (next_step_cells, True)
			if (current_row, current_col) in visited_cells:
				break
			next_step_cells.add((current_row, current_col))
	return (next_step_cells, False)

def sweep_adjacent_cells(grid, start_cell, target_cell, visited_cells):
	N = len(grid)
	cells_to_process = deque()
	cells_to_process.append(start_cell)
	for i in range(N * N):
		next_visit_set = set()
		while len(cells_to_process) > 0:
			cell = cells_to_process.popleft()
			visited_cells.add(cell)
			(next_step_cells, found) = add_next_step(grid, cell, target_cell, visited_cells)
			if found:
				return i + 1
			next_visit_set.update(next_step_cells)
		visited_cells.update(next_visit_set)
		cells_to_process.extend(next_visit_set)
	assert False
	return -1000000
N = int(get_input())
visited_cells = set()
grid = []
for row in range(N):
	grid.append(list(get_input().strip()))
for row in range(N):
	for col in range(len(grid[row])):
		if grid[row][col] == 'X':
			visited_cells.add((row, col))
(start_row, start_col, end_row, end_col) = [int(x) for x in get_input().split()]
result = sweep_adjacent_cells(grid, (start_row, start_col), (end_row, end_col), visited_cells)
print(result)
if PrintDebug:
	print_grid(grid)


N = int(input())
m = []
for _ in range(N):
	m.append(input())
[a, b, c, d] = map(int, input().split())

def neighbors(xy):
	(x, y) = xy
	for d in range(1, N):
		y2 = y + d
		if y2 >= N or m[x][y2] == 'X':
			break
		else:
			yield (x, y2)
	for d in range(1, N):
		y2 = y - d
		if y2 < 0 or m[x][y2] == 'X':
			break
		else:
			yield (x, y2)
	for d in range(1, N):
		x2 = x + d
		if x2 >= N or m[x2][y] == 'X':
			break
		else:
			yield (x2, y)
	for d in range(1, N):
		x2 = x - d
		if x2 < 0 or m[x2][y] == 'X':
			break
		else:
			yield (x2, y)
q = [((a, b), 0)]
visited = {(a, b)}
while q:
	cur = q.pop(0)
	if cur[0] == (c, d):
		print(cur[1])
		break
	else:
		ns = [n for n in neighbors(cur[0]) if n not in visited]
		visited.update(ns)
		q.extend(((n, cur[1] + 1) for n in ns))


N = int(input().strip())
grid = []
for i in range(N):
	row = []
	for e in input().strip():
		row.append(e)
	grid.append(row)
[a, b, c, d] = map(int, input().strip().split(' '))
turnRecord = [[0 for i in range(N)] for j in range(N)]
queue = []
grid[a][b] = 'X'
queue.append([a, b])
while len(queue) > 0:
	[curX, curY] = queue.pop(0)
	if curX == c and curY == d:
		break
	for dx in range(curX - 1, -1, -1):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dx in range(curX + 1, N):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dy in range(curY - 1, -1, -1):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
	for dy in range(curY + 1, N):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
print(turnRecord[c][d])


n_lines = int(input())
board = {}

def find_neighbors(board, pos, grid_size):
	neighbors = []
	(row, col) = pos
	right_col = col + 1
	while right_col <= grid_size - 1:
		if board[row, right_col][0] != 'X':
			neighbors.append([row, right_col])
			right_col += 1
		else:
			break
	left_col = col - 1
	while left_col >= 0:
		if board[row, left_col][0] != 'X':
			neighbors.append([row, left_col])
			left_col -= 1
		else:
			break
	up_row = row - 1
	while up_row >= 0:
		if board[up_row, col][0] != 'X':
			neighbors.append([up_row, col])
			up_row -= 1
		else:
			break
	down_row = row + 1
	while down_row <= grid_size - 1:
		if board[down_row, col][0] != 'X':
			neighbors.append([down_row, col])
			down_row += 1
		else:
			break
	return neighbors
for i in range(n_lines):
	line = input()
	for (line_i, el) in enumerate(line):
		board[i, line_i] = [el, 0]
s_and_e = input().split(' ')
start = [int(s_and_e[0]), int(s_and_e[1])]
end = [int(s_and_e[2]), int(s_and_e[3])]
from collections import deque

def shortest_path(start, end, board, grid_size):
	queue = deque([start])
	visited = {}
	while len(queue) > 0:
		popped = queue.popleft()
		visited[tuple(popped)] = True
		neighbors = find_neighbors(board, popped, grid_size)
		parent_lvl = board[tuple(popped)][1]
		if popped == end:
			return parent_lvl
		for neighbor in neighbors:
			if neighbor == end:
				return parent_lvl + 1
			if tuple(neighbor) not in visited and neighbor not in queue:
				board[tuple(neighbor)][1] = parent_lvl + 1
				visited[tuple(neighbor)] = True
				queue.append(neighbor)
print(shortest_path(start, end, board, n_lines))


N = int(input().strip())
grid = []
for i in range(N):
	row = []
	for e in input().strip():
		row.append(e)
	grid.append(row)
[a, b, c, d] = map(int, input().strip().split(' '))
turnRecord = [[0 for i in range(N)] for j in range(N)]
queue = []
grid[a][b] = 'X'
queue.append([a, b])
while len(queue) > 0:
	[curX, curY] = queue.pop(0)
	if curX == c and curY == d:
		break
	for dx in range(curX - 1, -1, -1):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dx in range(curX + 1, N):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dy in range(curY - 1, -1, -1):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
	for dy in range(curY + 1, N):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
print(turnRecord[c][d])


from collections import namedtuple
P = namedtuple('P', ['x', 'y'])
Node = namedtuple('Node', ['p', 'counter', 'parent'])
queue = list()
n = int(input())
ary = []
processed_nodes = {}

def processed(node):
	p = node.p
	if p in processed_nodes:
		if processed_nodes[p] <= node.counter:
			return True
	return False

def add_node(node):
	if ary[node.p.x][node.p.y] == 'X':
		return False
	if not processed(node):
		queue.insert(0, node)
		processed_nodes[node.p] = node.counter
	return True

def add_ajacent_nodes(node):
	add_nodes(node.p.x - 1, -1, -1, None, node.p.y, node)
	add_nodes(node.p.x + 1, n, 1, None, node.p.y, node)
	add_nodes(node.p.y - 1, -1, -1, node.p.x, None, node)
	add_nodes(node.p.y + 1, n, 1, node.p.x, None, node)

def add_nodes(start, end, incre, x, y, parent):
	for i in range(start, end, incre):
		to_continue = True
		new_node = None
		if x != None:
			new_node = Node(P(x, i), parent.counter + 1, parent)
		if y != None:
			new_node = Node(P(i, y), parent.counter + 1, parent)
		if new_node:
			to_continue = add_node(new_node)
			if not to_continue:
				break
		else:
			print('wrong', i, x, y)

def print_path(node):
	current = node
	while current:
		print((current.p, current.counter, ary[current.p.x][current.p.y]))
		current = current.parent
for _ in range(n):
	ary.append(input())
(a, b, c, d) = [int(i) for i in input().split()]
add_node(Node(P(c, d), 0, None))
found = None
while queue:
	node = queue.pop()
	if node.p == (a, b):
		found = node
		break
	add_ajacent_nodes(node)
print(found.counter)


N = int(input().strip())
grid = []
for i in range(N):
	row = []
	for e in input().strip():
		row.append(e)
	grid.append(row)
[a, b, c, d] = map(int, input().strip().split(' '))
turnRecord = [[0 for i in range(N)] for j in range(N)]
queue = []
grid[a][b] = 'X'
queue.append([a, b])
while len(queue) > 0:
	[curX, curY] = queue.pop(0)
	if curX == c and curY == d:
		break
	for dx in range(curX - 1, -1, -1):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dx in range(curX + 1, N):
		if grid[dx][curY] == 'X':
			break
		if grid[dx][curY] == '*':
			turnRecord[dx][curY] = min(turnRecord[dx][curY], turnRecord[curX][curY] + 1)
		else:
			grid[dx][curY] = '*'
			turnRecord[dx][curY] = turnRecord[curX][curY] + 1
			queue.append([dx, curY])
	for dy in range(curY - 1, -1, -1):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
	for dy in range(curY + 1, N):
		if grid[curX][dy] == 'X':
			break
		if grid[curX][dy] == '*':
			turnRecord[curX][dy] = min(turnRecord[curX][dy], turnRecord[curX][curY] + 1)
		else:
			grid[curX][dy] = '*'
			turnRecord[curX][dy] = turnRecord[curX][curY] + 1
			queue.append([curX, dy])
print(turnRecord[c][d])


import sys

class vertex:

	def __init__(self, id):
		self.id = id
		self.neighbors = {}
		self.distance = 0

class graph:

	def __init__(self):
		self.vertices = {}

	def addVertex(self, id):
		v = vertex(id)
		self.vertices[id] = v

	def addEdge(self, source, dest, w):
		if source not in self.vertices:
			self.addVertex(source)
		if dest not in self.vertices:
			self.addVertex(dest)
		self.vertices[source].neighbors[dest] = w
		self.vertices[dest].neighbors[source] = w

def getPointId(n, x, y):
	return n * x + y

def connect_right_nodes(grid, g, source, i, j, n):
	k = 1
	while j + k < n and grid[i][j + k] != 'X':
		g.addEdge(source, getPointId(n, i, j + k), 1)
		k += 1

def connect_bottom_nodes(grid, g, source, i, j, n):
	k = 1
	while i + k < n and grid[i + k][j] != 'X':
		g.addEdge(source, getPointId(n, i + k, j), 1)
		k += 1

def bfs(g, source, dest):
	for v in g.vertices.values():
		v.distance = sys.maxsize
	visited = {}
	for id in g.vertices:
		visited[id] = False
	g.vertices[source].distance = 0
	visited[source] = True
	q = []
	q.append(source)
	while q:
		nodeId = q.pop(0)
		if nodeId == dest:
			return g.vertices[nodeId].distance
		for (neighbor, dist) in g.vertices[nodeId].neighbors.items():
			if not visited[neighbor]:
				g.vertices[neighbor].distance = g.vertices[nodeId].distance + 1
				visited[neighbor] = True
				q.append(neighbor)
			elif g.vertices[neighbor].distance > g.vertices[nodeId].distance + 1:
				g.vertices[neighbor].distance = g.vertices[nodeId].distance + 1
n = int(input().strip())
grid = ['' for i in range(n)]
for i in range(n):
	grid[i] = input().strip()
(xi, yi, xf, yf) = [int(a) for a in input().strip().split()]
g = graph()
for i in range(n):
	for j in range(n):
		if grid[i][j] != 'X':
			source = getPointId(n, i, j)
			connect_right_nodes(grid, g, source, i, j, n)
			connect_bottom_nodes(grid, g, source, i, j, n)
print(bfs(g, getPointId(n, xi, yi), getPointId(n, xf, yf)))