Problem6133--传送阵

6133: 传送阵

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给定一个 $n \times n$ 的方格矩阵,行、列编号为 $1 \sim n$,其中第 $i$ 行第 $j$ 列的方格坐标为 $(i,\ j)$。
每个方格要么是平地,要么是陷阱。
旅行者从方格 $(r_1,\ c_1)$ 出发,要前往方格 $(r_2,\ c_2)$ 处。
出发点和目的地保证都是平地。
旅行者每次移动可以沿上、下、左、右四个方向,移动一格距离。
移动过程中,不得走出矩阵或进入陷阱。
由于存在陷阱的原因,旅行者可能无法顺利抵达目的地。
幸运的是,他可以任意选择两个平地方格,在上面建立一对传送阵。
传送阵能够支持旅行者在两个平地方格之间自由传送。
但是,建立传送阵是一笔不容小视的花费。
在方格 $(r_s,\ c_s)$ 和 $(r_t,\ c_t)$ 处建立传送阵,所需成本为 $(r_s−r_t)^2+(c_s−c_t)^2$。
请你计算,为了使旅行者能够成功抵达目的地,建立传送阵所需花费的最低成本。
如果旅行者可以无需建立传送阵,直接走到目的地,那么成本就是 $0$。
注意,最多只能建立一对传送阵。

Input

第一行包含整数 $n$,表示矩阵尺寸。
第二行包含两个整数 $r_1,\ c_1$,表示起点方格坐标为 $(r_1,\ c_1)$。
第三行包含两个整数 $r_2,\ c_2$,表示目的地方格坐标为 $(r_2,\ c_2)$。
接下来 $n$ 行,每行包含一个长度为 $n$ 的 $01$ 字符串,其中第 $i$ 行第 $j$ 个字符如果为 $0$,则表示方格 $(i,\ j)$ 是平地,如果为 $1$,则表示方格 $(i,\ j)$ 是陷阱。

Output

输出一个整数,表示为了确保旅行能够成功,所需花费的最小成本。

Constraints

前三个测试点满足,$1≤n≤10$。
所有测试点满足,$1≤n≤50,\ 1≤r_1,\ c_1,\ r_2,\ c_2≤n$。

Sample 1 Input

5
1 1
5 5
00001
11111
00111
00110
00110

Sample 1 Output

10

Sample 2 Input

3
1 3
3 1
010
101
010

Sample 2 Output

8

Sample 3 Input

1
1 1
1 1
0

Sample 3 Output

0

HINT

相同题目:AcWing

EDITORIAL

Source/Category