题目描述
大哈和小羽生活在由陆地和海洋组成的蔚蓝色星球,由于一次天地间的重大变故,导致这颗星球的地形与分布大变。当大哈和小羽醒来时,发现他们彼此之间已经分开了。现在大哈想要去寻找自己的爱人。如果还是在同一个大陆上,那他们终有一天会团圆。但如果他们之间有海洋的间隔,则可能永远也找不到对方。
现在,身为上帝的你于心不忍,所以打算为他们搭一座鹊桥,不过搭鹊桥需要消耗你的原力,所以你反复思量应该把鹊桥的两端设置在哪里。如果大哈和小羽本来就在同一个大陆上,那你就不需要搭鹊桥,也就是你花费的原力为
0
0。而如果他们之间有海洋做间隔,则你需要设置鹊桥的两端,假设一端设置在
(
�
1
,
�
1
)
(x
1
,y
1
)
) 这个点上,另一端设置在
(
�
2
,
�
2
)
(x
2
,y
2
) 这个点上,则你需要花费的原力为
(
�
2
−
�
1
)
2
+
(
�
2
−
�
1
)
2
(x
2
−x
1
)
2
+(y
2
−y
1
)
2
。
请算出你所需要花费的最少原力,使得大哈和小羽最终有能相聚的一天。
输入格式
第一行一个整数
�
n 代表地图的大小。
第二行两个整数
�
�
,
�
�
s
x
,s
y
代表大哈的位置。
第三行两个整数
�
�
,
�
�
e
x
,e
y
代表小羽的位置。
接下来给出
�
×
�
n×n 的
01
01 矩阵,代表地图。
0
0 代表陆地,
1
1 代表海洋。
当两块陆地在上、下、左、右四个方向上相邻时,认为是一块陆地。
输出格式
一个整数,代表最少需要花费的原力。
样例
输入数据#1
5
1 1
5 5
00001
11111
00111
00110
00110
Copy
输出数据#1
10
Copy
输入数据#2
3
1 3
3 1
010
101
010
Copy
输出数据#2
8
Copy
数据范围
对于
10
%
10% 的测试点
�
=
2
n=2。
另有
30
%
30% 的测试点
�
≤
10
n≤10。
所有测试点均满足:
1
≤
�
≤
1000
1≤n≤1000,
1
≤
�
�
,
�
�
,
�
�
,
�
�
≤
�
1≤s
x
,s
y
,e
x
,e
y
≤n。