6133: 传送阵
[Creator : ]
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$。
注意,最多只能建立一对传送阵。
每个方格要么是平地,要么是陷阱。
旅行者从方格 $(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)$ 是陷阱。
第二行包含两个整数 $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$。
所有测试点满足,$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。