Alice lives on a flat planet that can be modeled as a square grid of size $n \times n$, with rows and columns enumerated from $1$ to $n$. We represent the cell at the intersection of row $r$ and column $c$ with ordered pair $(r, c)$. Each cell in the grid is either land or water.

 [Image] An example planet with $n = 5$. It also appears in the first sample test. 

Alice resides in land cell $(r_1, c_1)$. She wishes to travel to land cell $(r_2, c_2)$. At any moment, she may move to one of the cells adjacent to where she is—in one of the four directions (i.e., up, down, left, or right).

Unfortunately, Alice cannot swim, and there is no viable transportation means other than by foot (i.e., she can walk only on land). As a result, Alice's trip may be impossible.

To help Alice, you plan to create at most one tunnel between some two land cells. The tunnel will allow Alice to freely travel between the two endpoints. Indeed, creating a tunnel is a lot of effort: the cost of creating a tunnel between cells $(r_s, c_s)$ and $(r_t, c_t)$ is $(r_s-r_t)^2 + (c_s-c_t)^2$.

For now, your task is to find the minimum possible cost of creating at most one tunnel so that Alice could travel from $(r_1, c_1)$ to $(r_2, c_2)$. If no tunnel needs to be created, the cost is $0$.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 50$) — the width of the square grid.

The second line contains two space-separated integers $r_1$ and $c_1$ ($1 \leq r_1, c_1 \leq n$) — denoting the cell where Alice resides.

The third line contains two space-separated integers $r_2$ and $c_2$ ($1 \leq r_2, c_2 \leq n$) — denoting the cell to which Alice wishes to travel.

Each of the following $n$ lines contains a string of $n$ characters. The $j$-th character of the $i$-th such line ($1 \leq i, j \leq n$) is 0 if $(i, j)$ is land or 1 if $(i, j)$ is water.

It is guaranteed that $(r_1, c_1)$ and $(r_2, c_2)$ are land.


-----Output-----

Print an integer that is the minimum possible cost of creating at most one tunnel so that Alice could travel from $(r_1, c_1)$ to $(r_2, c_2)$.


-----Examples-----
Input
5
1 1
5 5
00001
11111
00111
00110
00110

Output
10

Input
3
1 3
3 1
010
101
010

Output
8



-----Note-----

In the first sample, a tunnel between cells $(1, 4)$ and $(4, 5)$ should be created. The cost of doing so is $(1-4)^2 + (4-5)^2 = 10$, which is optimal. This way, Alice could walk from $(1, 1)$ to $(1, 4)$, use the tunnel from $(1, 4)$ to $(4, 5)$, and lastly walk from $(4, 5)$ to $(5, 5)$.

In the second sample, clearly a tunnel between cells $(1, 3)$ and $(3, 1)$ needs to be created. The cost of doing so is $(1-3)^2 + (3-1)^2 = 8$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
a = [['1'] * (n + 2)]
for _ in range(n):
    s = input()
    d = ['1']
    for i in s:
        d.append(i)
    d.append('1')
    a.append(d)
a.append(['1'] * (n + 2))
s = []
f = []
q = [[r1, c1]]
while q:
    x, y = q.pop()
    a[x][y] = '1'
    s.append([x, y])
    if a[x - 1][y] == '0':
        q.append([x - 1, y])
    if a[x][y - 1] == '0':
        q.append([x, y - 1])
    if a[x + 1][y] == '0':
        q.append([x + 1, y])
    if a[x][y + 1] == '0':
        q.append([x, y + 1])
if [r2, c2] in s:
    print(0)
else:
    q = [[r2, c2]]
    while q:
        x, y = q.pop()
        a[x][y] = '1'
        f.append([x, y])
        if a[x - 1][y] == '0':
            q.append([x - 1, y])
        if a[x][y - 1] == '0':
            q.append([x, y - 1])
        if a[x + 1][y] == '0':
            q.append([x + 1, y])
        if a[x][y + 1] == '0':
            q.append([x, y + 1])
    res = 10**10
    for i in s:
        for j in f:
            res = min(res, (i[0] - j[0])**2 + (i[1] - j[1])**2)
    print(res)

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


n=nn()

r1, c1=mi()

r2, c2=mi()

r1=r1-1
c1=c1-1
r2=r2-1
c2=c2-1



g=[]

for i in range(n):
	g.append(li())

#print(g)


cc1=set()


stack=[(r1,c1)]

while stack:
	#print(stack)
	r,c=stack.pop()
	cc1.add((r,c))
	for i in range(-1,2):
		for j in range(-1,2):
			if not (i==0 and j==0):
				if i==0 or j==0:
					if r+i in range(0,n) and c+j in range(0,n):
						if not (r+i,c+j) in cc1:							
							if g[r+i][c+j]=='0':
								stack.append((r+i,c+j))


cc2=set()


stack=[(r2,c2)]

while stack:
	r,c=stack.pop()
	cc2.add((r,c))
	for i in range(-1,2):
		for j in range(-1,2):
			if not (i==0 and j==0):
				if i==0 or j==0:
					if r+i in range(0,n) and c+j in range(0,n):
						if not (r+i,c+j) in cc2:					
							if g[r+i][c+j]=='0':
							
								stack.append((r+i,c+j))

	
#print(cc1,cc2)
dist=10*n*n

for x,y in cc1:
	for x1, y1 in cc2:
		d=(x-x1)**2+(y-y1)**2
		dist=min(d,dist)

print(dist)
		


import sys
sys.setrecursionlimit(100000)
def hypot(a, b):
    return a ** 2 + b ** 2


def bfs0(r, c):
    nonlocal used
    used[r][c] = True
    comp0.append((r, c))
    if r > 0:
        if not used[r - 1][c] and matr[r - 1][c]:
            bfs0(r - 1, c)
    if r < n - 1:
        if not used[r + 1][c] and matr[r + 1][c]:
            bfs0(r + 1, c)
    if c > 0:
        if not used[r][c - 1] and matr[r][c - 1]:
            bfs0(r, c - 1)
    if c < n - 1:
        if not used[r][c + 1] and matr[r][c + 1]:
            bfs0(r, c + 1)


def bfs1(r, c):
    nonlocal used
    used[r][c] = True
    comp1.append((r, c))
    if r > 0:
        if not used[r - 1][c] and matr[r - 1][c]:
            bfs1(r - 1, c)
    if r < n - 1:
        if not used[r + 1][c] and matr[r + 1][c]:
            bfs1(r + 1, c)
    if c > 0:
        if not used[r][c - 1] and matr[r][c - 1]:
            bfs1(r, c - 1)
    if c < n - 1:
        if not used[r][c + 1] and matr[r][c + 1]:
            bfs1(r, c + 1)


n = int(input())
r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
matr = [[] for i in range(n)]
for i in range(n):
    for el in input():
        if el == '0':
            matr[i].append(True)
        else:
            matr[i].append(False)
# print(matr)
used = [[False] * n for i in range(n)]
comp0 = []
bfs0(r1 - 1, c1 - 1)
if used[r2 - 1][c2 - 1]:
    print(0)
else:
    comp1 = []
    mi = 100000000000000
    bfs1(r2 - 1, c2 - 1)
    for el in comp0:
        for ell in comp1:
            mi = min(hypot(ell[0] - el[0], ell[1] - el[1]), mi)
    print(mi)

'''input
3
1 3
3 1
010
101
010
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


def valid(i,j):
	if i<0 or i>=n:
		return 0
	if j<0 or j>=n:
		return 0
	#print(i,j,mat)
	if vis[i][j]==1 or mat[i][j]=="1":
		return 0
	return 1

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

def bfs(i,j):
	one=[(i,j)]
	vis[i][j]=1
	s=[(i,j)]
	while s:
		x,y=s.pop(-1)
		for k in range(4):
			if valid(x+dx[k],y+dy[k]):
				vis[x+dx[k]][y+dy[k]]=1
				s.append((x+dx[k],y+dy[k]))
				one.append((x+dx[k],y+dy[k]))
	return one


n=ri(1)
x1,y1=[int(i)-1 for i in input().split()]
x2,y2=[int(i)-1 for i in input().split()]

mat=[]
vis=[[0 for i in range(n)] for j in range(n)]

for i in range(n):
	mat.append(list(input()))

one=bfs(x1,y1)
two=bfs(x2,y2)

ans=999999999999

for i,j in one:
	for p,q in two:
		ans=min(ans,(i-p)**2+(j-q)**2)
print(ans)

n = int(input())
r1,c1 = list(map(int, input().split()))
r2,c2 = list(map(int, input().split()))

r1 -=1
c1 -=1
r2 -=1
c2 -=1
g = []
for i in range(n):
    g.append(input())

d1 = {(r1,c1)}
q = [(r1,c1)]
while q:
    v = q[0]
    r,c = v
    if r == r2 and c == c2:
        print(0)
        return
    q = q[1:]
    if r+1 >=0 and r+1 < n:
        nv = (r+1, c)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d1:
                d1.add(nv)
                q.append(nv)
    if r-1 >=0 and r-1 < n:
        nv = (r-1, c)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d1:
                d1.add(nv)
                q.append(nv)
    if c+1 >=0 and c+1 < n:
        nv = (r, c+1)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d1:
                d1.add(nv)
                q.append(nv)
    if c-1 >=0 and c-1 < n:
        nv = (r, c-1)
        if g[nv[0]][nv[1]] =='0':
            if nv not in d1:
                d1.add(nv)
                q.append(nv)

d2 = {(r2, c2)}
q = [(r2,c2)]
while q:
    v = q[0]
    r,c = v
    q = q[1:]
    if r+1 >=0 and r+1 < n:
        nv = (r+1, c)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d2:
                d2.add(nv)
                q.append(nv)
    if r-1 >=0 and r-1 < n:
        nv = (r-1, c)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d2:
                d2.add(nv)
                q.append(nv)
    if c+1 >=0 and c+1 < n:
        nv = (r, c+1)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d2:
                d2.add(nv)
                q.append(nv)
    if c-1 >=0 and c-1 < n:
        nv = (r, c-1)
        if g[nv[0]][nv[1]] == '0':
            if nv not in d2:
                d2.add(nv)
                q.append(nv)
ans = 10**18
for v1 in d1:
    for v2 in d2:
        ans = min(ans, (v1[0] - v2[0])**2 + (v1[1] - v2[1])**2)
print(ans)



import sys
sys.setrecursionlimit(100000)

N = int(input())
r1, c1 = list(map(int, input().split()))
r2, c2 = list(map(int, input().split()))
r1 -= 1
c1 -= 1
r2 -= 1
c2 -= 1

A = [[int(a) for a in input()] for i in range(N)]

X = [[0] * N for _ in range(N)]
L = []
def dfs(r, c):
    move = [[0,1], [0,-1], [-1,0], [1,0]]
    X[r][c] = 1
    L.append((r, c))
    for m in move:
        nr, nc = r+m[0], c+m[1]
        if nr >= 0 and nr < N and nc >= 0 and nc < N:
            if X[nr][nc] == 0 and A[nr][nc] == 0:
                dfs(nr, nc)
        
dfs(r1, c1)

if X[r2][c2]:
    print(0)
else:
    LL = [l for l in L]
    
    L = []
    dfs(r2, c2)
    
    mi = 10**10
    for ll in LL:
        for l in L:
            mi = min((ll[0]-l[0])**2+(ll[1]-l[1])**2, mi)
    
    print(mi)



def add(ans, r, c):
    if cells[r][c] == '0':
        cells[r][c] = '1'
        rc = r, c
        ans.append(rc)


def dfs(r, c):
    ans = [(r, c)]
    for r, c in ans:
        if c != 1:
            add(ans, r, c - 1)
        if c != n:
            add(ans, r, c + 1)
        if r != 1:
            add(ans, r - 1, c)
        if r != n:
            add(ans, r + 1, c)
    return ans


n = int(input())
r1, c1 = list(map(int, input().split()))
r2, c2 = list(map(int, input().split()))
res = 5000  # n ** 2 * 2
cells = (['1'],) + tuple((['1'] + list(input()) for _ in range(n)))
dfs1 = dfs(r1, c1)
for rs, cs in dfs(r2, c2):
    for rt, ct in dfs1:
        res = min(res, (rs - rt) ** 2 + (cs - ct) ** 2)
print(res)


n = int(input())
r1,c1 = list(map(int,input().split()))
r2,c2 = list(map(int,input().split()))
r1-=1
r2-=1
c1-=1
c2-=1
maze = []
for i in range(n):
	maze.append(input())
list1 = [(r1,c1)]
list2 = [(r2,c2)]
tovisit = [(r1,c1)]
while len(tovisit)>0:
	x,y = tovisit.pop()
	for cx,cy in [(0,1),(0,-1),(1,0),(-1,0)]:
		if x+cx >= 0 and y+cy >= 0 and x+cx < n  and y+cy < n and (x+cx, y+cy) not in list1 and maze[x+cx][y+cy] == "0":
			list1.append((x+cx, y+cy))
			tovisit.append((x+cx, y+cy))
if (r2,c2) in list1:
	print(0)
	return
tovisit = [(r2,c2)]
while len(tovisit)>0:
	x,y = tovisit.pop()
	for cx,cy in [(0,1),(0,-1),(1,0),(-1,0)]:
		if x+cx >= 0 and y+cy >= 0 and x+cx < n  and y+cy < n and (x+cx, y+cy) not in list2 and maze[x+cx][y+cy] == "0":
			list2.append((x+cx, y+cy))
			tovisit.append((x+cx, y+cy))
mini = 30000000
for i in list1:
	for i2 in list2:
		ans = (i[0] - i2[0])**2 + (i[1] - i2[1])**2
		mini = min(mini,ans)
print(mini)


def dis(u,v):
    x1,y1=u
    x2,y2=v
    return(( (x1-x2)**2 + (y1-y2)**2 ))


def adj(u):
    x,y=u
    t=[]
    #print(x,y)
    if x+1<n and a[x+1][y]=='0':
        t.append([x+1,y])
    if y+1<n and a[x][y+1]=='0':
        t.append([x,y+1])
    if x-1>=0 and a[x-1][y]=='0':
        t.append([x-1,y])
    if y-1>=0 and a[x][y-1]=='0':
        t.append([x,y-1])
    return(t)

def bfs(s):
    ans=[s]
    x,y=s
    v2[x][y]=1
    frontier=[s]
    while frontier:
        nex=[]
        for u in frontier:
            for v in adj(u):
                if v2[v[0]][v[1]]==0:
                    nex.append(v)
                    v2[v[0]][v[1]]=1
                    ans.append(v)
        frontier=nex
    return(ans)


n=int(input())
r1,c1=[int(i) for i in input().split(' ')]
r2,c2=[int(i) for i in input().split(' ')]
a=[]
for i in range(n):
    a.append(list(input()))

v2=[[0 for i in range(n)] for j in range(n)]

ans1=bfs([r1-1,c1-1])
ans2=bfs([r2-1,c2-1])
r=9999999999
for i in ans1:
    for j in ans2:
        #print(i,j)
        r=min(r,dis(i,j))
print(r)




from collections import deque


def BFS(a, vertex=None):
    if vertex is None:
        vertex = 1
    s = [1]*len(a)
    d = deque([vertex])
    s[vertex] = 0
    f = {vertex}
    while len(d) > 0:
        for q in a[d.popleft()]:
            if s[q]:
                d.append(q)
                f.add(q)
                s[q] = 0
    return f


def components(a):
    s = [1]*len(a)
    d, q2 = [], 1
    while q2 < len(a):
        if s[q2]:
            if len(a[q2]) == 0:
                s[q2] = 0
                d.append({q2})
            else:
                f = BFS(a, q2)
                d.append(f)
                for q in f:
                    s[q] = 0
        else:
            q2 += 1
    return d


n = int(input())
x1, y1 = list(map(int, input().split()))
x2, y2 = list(map(int, input().split()))
a = [[0]*(n+2)]+[[0]+list(map(int, [1-int(q) for q in list(input())]))+[0] for _ in range(n)]+[[0]*(n+2)]
d = [[] for _ in range(n**2+1)]
for q in range(1, n+1):
    for q1 in range(1, n+1):
        if a[q][q1]:
            if a[q-1][q1]:
                d[(q-1)*n+q1].append((q-2)*n+q1)
            if a[q+1][q1]:
                d[(q-1)*n+q1].append(q*n+q1)
            if a[q][q1-1]:
                d[(q-1)*n+q1].append((q-1)*n+q1-1)
            if a[q][q1+1]:
                d[(q-1)*n+q1].append((q-1)*n+q1+1)
x, y = (x1-1)*n+y1, (x2-1)*n+y2
s = components(d)
comp_x, comp_y = [], []
for q in s:
    if x in q:
        comp_x = q
    if y in q:
        comp_y = q
if comp_y == comp_x:
    print(0)
else:
    ans = float('inf')
    for q in comp_x:
        for q1 in comp_y:
            x1, x2, y1, y2 = (q-1)//n+1, (q-1) % n+1, (q1-1)//n+1, (q1-1) % n+1
            ans = min((x1-y1)**2+(x2-y2)**2, ans)
    print(ans)


from collections import deque
n = int(input())

r1, c1 = (int(t)-1 for t in input().split(' '))
r2, c2 = (int(t)-1 for t in input().split(' '))

mx = [input() for _ in range(n)]

visited = [[0] * n for _ in range(n)]

def bfs(start, mark):
    q = deque()
    q.append(start)


    while len(q):
        r, c = q.popleft()
        if visited[r][c]: continue
        visited[r][c] = mark

        dirs = [(t[0] + r, t[1] + c) for t in [(0, 1), (1, 0), (-1, 0), (0, -1)] if t[0] + r < n and t[0] + r >= 0 and t[1] + c < n and t[1] + c >= 0]

        dirs = [d for d in dirs if not visited[d[0]][d[1]] and mx[d[0]][d[1]] == '0']
        for d in dirs:
            q.append(d)

bfs((r1, c1), 1)
if visited[r2][c2] == 1:
    print(0)
else:
    bfs((r2, c2), 2)
    firsts = [(i, j) for i in range(n) for j in range(n) if visited[i][j] == 1]
    seconds = [(i, j) for i in range(n) for j in range(n) if visited[i][j] == 2]
    result = min((f[0] - s[0])**2 + (f[1] - s[1])**2 for f in firsts for s in seconds)
    print(result)


n = int(input())
r1, c1 = map(int, input().split())
r1, c1 = r1 - 1, c1 - 1
r2, c2 = map(int, input().split())
r2, c2 = r2 - 1, c2 - 1
T = [[] for i in range(n)]
for i in range(n):
    a = list(input())
    T[i] = a

k = 0
G = [[] for i in range(n * n)]
for i in range(n):
    for j in range(n):
        if T[i][j] == '0':
            que = [(i, j, k)]
            while que:
                x, y, d = que.pop()
                G[d].append((x, y))
                T[x][y] = '1'
                for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and T[nx][ny] == '0':
                        T[nx][ny] = '1'
                        que.append((nx, ny, d))
            k += 1

s = -1
e = -1
for k in range(n * n):
    if (r1, c1) in G[k]:
        s = k
    if (r2, c2) in G[k]:
        e = k

num = float('inf')
for sx, sy in G[s]:
    for ex, ey in G[e]:
        num = min(num, abs(sx - ex) ** 2 + abs(sy - ey) ** 2)

print(num)

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n = int(input())
r1, c1 = [int(i) for i in input().split()]
r2, c2 = [int(i) for i in input().split()]
MAP = [[int(s) for s in input()] for i in range(n)]
r1 -= 1
c1 -= 1
r2 -= 1
c2 -= 1

def dfs(r, c, mark, A):
    if r < 0 or r >= n or c < 0 or c >= n:
        return
    if MAP[r][c] == 1:
        return
    if MAP[r][c] == mark:
        return
    A.append((r, c))
    MAP[r][c] = mark
    for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        dfs(r+dr, c+dc, mark, A)

A = []
dfs(r1, c1, 2, A)
if MAP[r1][c1] == MAP[r2][c2]:
    print(0)
    return
B = []
dfs(r2, c2, 3, B)

ans = 2 * n ** 2
for a, b in A:
    ans = min(ans, min((a - c) ** 2 + (b - d) ** 2 for c, d in B))

print(ans)

from sys import setrecursionlimit
import threading

setrecursionlimit(10 ** 9)
threading.stack_size(67108864)


def main():
    dr = [[1, 0], [0, 1], [-1, 0], [0, -1]]


    def dfs(v, i):
        used[v[0]][v[1]] = i
        cm[i - 1] += [v]
        for x in dr:
            u = [v[0] + x[0], v[1] + x[1]]
            if a[u[0]][u[1]] == 0 and used[u[0]][u[1]] == 0:
                dfs(u, i)


    n = int(input())
    s = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a = [list(map(int, list(input()))) + [1] for i in range(n)]
    used = [[0] * n for i in range(n)]
    cm = [[], []]
    a += [[1] * n]
    s[0] -= 1
    s[1] -= 1
    f[0] -= 1
    f[1] -= 1
    dfs(s, 1)
    if used[f[0]][f[1]] == 1:
        print(0)
        return
    dfs(f, 2)
    ans = 10000
    for p1 in cm[0]:
        for p2 in cm[1]:
            ans = min(ans, (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    print(ans)


thread = threading.Thread(target=main)
thread.start()

import sys
sys.setrecursionlimit(0x20000000)
def dfs(i,j,vis,g,c):
	vis[i][j]=1
	c.append((i,j))
	"""
	if i>0 and 
		if j>0 and vis[i-1][j-1]==0:
			dfs(i-1,j-1,vis,g,c)
		if j<n-1 and vis[i-1][j+1]==0:
				dfs(i-1,j+1,vis,g,c)
	if i>0 and j<n-1 and vis[i-1][j+1]==0:
		dfs(i-1,j+1,vis,g,c)
	if i<n-1 and j>0 and vis[i+1][j-1]==0:
		dfs(i+1,j-1,vis,g,c)
	if i<n-1 and j<n-1 and vis[i+1][j+1]==0:
		dfs(i+1,j+1,vis,g,c)
	"""
	if i>0 and vis[i-1][j]==0 and g[i-1][j]=="0":
		dfs(i-1,j,vis,g,c)
	if i<n-1 and vis[i+1][j]==0 and g[i+1][j]=="0":
		dfs(i+1,j,vis,g,c)
	if j<n-1 and vis[i][j+1]==0 and g[i][j+1]=="0":
		dfs(i,j+1,vis,g,c)
	if  j>0 and vis[i][j-1]==0 and g[i][j-1]=="0":
		dfs(i,j-1,vis,g,c)

n=int(input())
r1,c1=map(int,input().split())
r1-=1
c1-=1
r2,c2=map(int,input().split())
r2-=1
c2-=1
# a=list(map(int,input().split()))
g=[]
for i in range(n):
	g.append(input())

vis=[[0 for i in range(n)] for i in range(n)]
com1=[]
dfs(r1,c1,vis,g,com1)
com2=[]
dfs(r2,c2,vis,g,com2)
#print(com1,com2)
m=1000000000000
for i in com1:
	for j in com2:
		d=(i[0]-j[0])**2+(i[1]-j[1])**2
		m=min(m,d)
print(m)

from collections import deque
from heapq import heappush, heappop
N = int(input())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
square = ["2"*(N+2)] + ["2"+input()+"2" for _ in [0]*N] + ["2"*(N+2)]


def bfs(startx, starty, v, goal=None):

    if v == 1:
        visited = [[0]*(N+2) for _ in [0]*(N+2)]
        visited[starty][startx] = 1
        s = set()
        add = s.add
        dq = deque([(startx, starty)])
        append, popleft = dq.append, dq.popleft

        while dq:
            x, y = popleft()
            add((x, y))
            for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                if square[ny][nx] == "0" and not visited[ny][nx]:
                    visited[ny][nx] = 1
                    append((nx, ny))

        return s
    else:
        visited = [[10**9]*(N+2) for _ in [0]*(N+2)]
        visited[starty][startx] = 0
        heap = [(0, startx, starty)]
        while heap:
            cost, x, y = heappop(heap)
            if (x, y) in goal:
                return (x, y)
            for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                new_cost = abs(nx-startx)**2 + abs(ny-starty)**2
                if square[ny][nx] != "2" and visited[ny][nx] > new_cost:
                    visited[ny][nx] = new_cost
                    heappush(heap, (new_cost, nx, ny))

        return (10**9, 10**9)


s1 = bfs(sx, sy, 1)
s2 = bfs(gx, gy, 1)
if s1 == s2:
    print(0)
    return

ans = 10**9
for x, y in s1:
    for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
        if square[ny][nx] == "1":
            destx, desty = bfs(nx, ny, 2, s2)
            dist = abs(x-destx)**2 + abs(y-desty)**2
            if ans > dist:
                ans = dist

print(ans)

from collections import deque

n = int(input())
y1, x1 = list(map(int, input().split(' ')))
y2, x2 = list(map(int, input().split(' ')))
y1 -= 1
x1 -= 1
y2 -= 1
x2 -= 1

dat = [input() for _ in range(n)]

bfs1 = [-1] * ((n + 1) * (n + 1))
bfs2 = [-1] * ((n + 1) * (n + 1))

def bfs(res, ys, xs):
    nonlocal dat, n
    d = deque()
    d.append([ys, xs, 0])

    while len(d) != 0:
        y, x, pr = d.popleft()

        if y == -1 or x == -1 or y >= n or x >= n:
            continue

        if dat[y][x] == '1':
            continue

        id = y * n + x
        if res[id] != -1 and res[id] <= pr:
            continue

        res[id] = pr
        pr += 1
        d.append([y + 0, x - 1, pr])
        d.append([y + 0, x + 1, pr])
        d.append([y - 1, x + 0, pr])
        d.append([y + 1, x + 0, pr])

bfs(bfs1, y1, x1)
bfs(bfs2, y2, x2)

if bfs1[y2 * n + x2] != -1:
    print(0)
    return

best = 1000000000000

def pow2(x):
    return x * x

for ys in range(n):
    for xs in range(n):
        ids = ys * n + xs
        if bfs1[ids] == -1:
            continue

        for ye in range(n):
            for xe in range(n):
                ide = ye * n + xe
                if bfs2[ide] == -1:
                    continue

                price = pow2(xs - xe) + pow2(ys - ye)
                best = min(best, price)

print(best)


# -*- coding: utf-8 -*-
# @Time    : 2019/2/25 0:05
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Connect.py

from collections import deque


def floodfill(x, y, grid, mark):
    if grid[x][y] != '0':
        return

    n = len(grid)
    queue = deque()
    queue.append((x, y))

    while queue:
        cx, cy = queue[0]
        queue.popleft()
        if grid[cx][cy] == mark:
            continue
        grid[cx][cy] = mark

        for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + d[0], cy + d[1]
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == '0':
                queue.append((nx, ny))


def main():
    n = int(input())
    r1, c1 = list(map(int, input().split()))
    r2, c2 = list(map(int, input().split()))
    r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1

    grid = []
    for _ in range(n):
        grid.append(list(input()))

    floodfill(r1, c1, grid, '*')
    floodfill(r2, c2, grid, '-')
    # for i in range(n):
    #     print(grid[i])

    if grid[r1][c1] == grid[r2][c2]:
        print(0)
    else:
        pos1, pos2 = [], []
        for i in range(n):
            for j in range(n):
                if grid[i][j] == '*':
                    pos1.append((i, j))
                elif grid[i][j] == '-':
                    pos2.append((i, j))

        ret = float('inf')
        # print(len(pos1))
        # print(len(pos2))
        for rs, cs in pos1:
            for rt, ct in pos2:
                ret = min(ret, (rt - rs) ** 2 + (ct - cs) ** 2)
        print(int(ret))


def __starting_point():
    main()

__starting_point()

n = int(input())
r1, c1 = list(map(int, input().split()))
r2, c2 = list(map(int, input().split()))
r1, c1, r2, c2 = r1-1, c1-1, r2-1, c2-1
g = []
for i in range(n):
    g.append(list(map(int, list(input()))))
from_r1 = set()
from_r2 = set()
x = [0, 1, 0, -1]
y = [1, 0, -1, 0]
visited = [[False for i in range(n)] for j in range(n)]

stack = [(r1, c1)]
while stack:
    v = stack.pop()
    if v[0] == r2 and v[1] == c2:
        print(0)
        return
    visited[v[0]][v[1]] = True
    for i in range(4):
        if v[0] + x[i] < n and v[1] + y[i] < n and v[0] + x[i] >= 0 and v[1] + y[i]>= 0 and not visited[v[0] + x[i]][v[1] + y[i]]:
            if g[v[0] + x[i]][v[1] + y[i]] == 0:
                stack.append((v[0]+x[i], v[1]+y[i]))
            else:
                from_r1.add((v[0], v[1]))


visited = [[False for i in range(n)] for j in range(n)]
stack = [(r2, c2)]
while stack:
    v = stack.pop()
    visited[v[0]][v[1]] = True
    for i in range(4):
        if v[0] + x[i] < n and v[1] + y[i] < n and v[0] + x[i] >= 0 and v[1] + y[i] >= 0 and not visited[v[0] + x[i]][v[1] + y[i]]:
            if g[v[0] + x[i]][v[1] + y[i]] == 0:
                stack.append((v[0]+x[i], v[1]+y[i]))
            else:
                from_r2.add((v[0], v[1]))

min_value = 100000000
for i in from_r1:
    for j in from_r2:
        min_value = min((i[0] - j[0])**2 + (i[1] - j[1])**2, min_value)
print(min_value)



import sys
input=sys.stdin.readline
sys.setrecursionlimit(99999)

n=int(input())
x,y=map(int,input().split())
r,c=map(int,input().split())
adj=[list(map(int,input().rstrip()))for _ in range(n)]

dx=[0,0,-1,1]
dy=dx[::-1]
valid=lambda x,y:0<=x<n and 0<=y<n
visit=[[False]*51 for _ in range(51)]
def dfs(x,y,ans):
    if visit[x][y]:return
    visit[x][y]=True
    ans.append((x,y))
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if not valid(nx,ny):continue
        if adj[nx][ny]:continue
        dfs(nx,ny,ans)
start=[];end=[]
dfs(x-1,y-1,start)
if (r-1,c-1) in start:
    print(0)
    return
dfs(r-1,c-1,end)


ans=10**100
for x,y in start:
    for a,b in end:
        ans=min(ans, (a-x)**2+(y-b)**2)
print(ans)

from collections import deque
import sys

n = int(input())
r1, c1 = map(lambda x : int(x) - 1, input().split())
r2, c2 = map(lambda x : int(x) - 1, input().split())

graph = []
components = []
land_components = {}

visited = set()

for i in range(n):
    row = input()
    graph.append(row)

def find_component(r, c):
    q = deque()
    q.append((r, c))
    queued = set()
    queued.add((r, c))
    result = []

    while q:
        cell = q.popleft()
        result.append(cell)

        consider = []

        r, c = cell

        if r > 0 and graph[r - 1][c] == '0':
            consider.append((r - 1, c))
        if c > 0 and graph[r][c - 1] == '0':
            consider.append((r, c - 1))
        if r < n - 1 and graph[r + 1][c] == '0':
            consider.append((r + 1, c))
        if c < n - 1 and graph[r][c + 1] == '0':
            consider.append((r, c + 1))
        for candidate in consider:
            if candidate not in queued:
                q.append(candidate)
                queued.add(candidate)

    return result

comp1 = find_component(r1, c1)
if (r2, c2) in comp1:
    print(0)
    return

comp2 = find_component(r2, c2)

best = None

for tuple1 in comp1:
    for tuple2 in comp2:
        dist = pow(tuple1[0] - tuple2[0], 2) + pow(tuple1[1] - tuple2[1], 2)
        if not best or best > dist:
            best = dist

print(best)

n, = map(int, input().split())

rs,cs = map(int, input().split())
rd,cd = map(int, input().split())
rs-=1
cs-=1
rd-=1
cd-=1


E = []
for i in range(0,n):
    E.append(list(input().split('\n')[0]))

S = []
D = []

import queue
q = queue.Queue()
q.put((rs, cs))


def get_all_dirs(e):
    dirs = []
    a,b = e[0], e[1]
    if a+1<n:
        dirs.append((a+1, b))
    if a-1>=0:
        dirs.append((a-1, b))
    if b+1<n:
        dirs.append((a, b+1))
    if b-1>=0:
        dirs.append((a,b-1))
    return dirs


def process_dirs(e):
    dirs = get_all_dirs(e)
    water = False
    for d in dirs:
        if E[d[0]][d[1]] == '1':
            water = True
        elif E[d[0]][d[1]] == '0':
            q.put(d)
            E[d[0]][d[1]] = '2'
    return water

while not q.empty():
    e = q.get()
    water = process_dirs(e)
    if e[0] == rd and e[1] == cd:
        print(0)
        return
    if water:
        S.append(e)


q.put((rd, cd))

while not q.empty():
    e = q.get()
    water = process_dirs(e)
    if water:
        D.append(e)

import sys
def square(a):
    return a*a

def dis(a, b):
    return square(a[0]-b[0]) + square(a[1]-b[1])

ans = sys.maxsize
for i in S:
    for j in D:
        ans = min(ans, dis(i,j))

print(ans)