题目描述

爱丽丝是一个出色的特工，可是她不会游泳。

为了营救她的同伴，她偷偷潜入了敌国阵地，敌国阵地是一个 \(N×N\) 个小正方形组成的大正方形。我们使用行号和列号给每个小正方形编号，行号从上到下、列号从左到右依次编号为 \(1\) ~ \(N\)。有的小方格是陆地，标记为 \(0\)；有的小方格是湖，标记为 \(1\)。

起初爱丽丝潜入地点是 \(r_1\) 行 \(c_1\) 列，记为 \((r_1,c_1)\)。被营救的同伴被关在 \(r_2\) 行 \(c_2\) 列，记为 \((r_2,c_2)\)。

爱丽丝可以向上下左右任一方向移动，前提是都是陆地。可惜的是仅仅在陆地上移动，不一定能够从 \((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\)。

你最多只能帮助爱丽丝打通一个传送门，请你计算出最少需要的成本。如果不用打通传送门，爱丽丝就能从 \((r1,c1)\) 到达 \((r2,c2)\)，则成本为 \(0\)。 .

格式

输入格式

第 \(1\) 行包含一个整数 \(N（1≤N≤100）\)。

第 \(2\) 行包含两个整数 \(r_1\) 和 \(c_1\)，以空格隔开。

第 \(3\) 行包含两个整数 \(r_2\) 和 \(c_2\)，以空格隔开。

以下 \(N\) 行，第 \(i\) 行一个 \(01\) 串，其中第 \(j\) 个字符，表示敌国阵地第 \(i\) 行第 \(j\) 列的小正方形是陆地（用 \(0\) 表示）还是湖（用 \(1\) 表示）。

输出格式

输出仅一行，一个整数，表示你所搭建传送门的最低成本。

样例1

样例输入1

5
1 1
5 5
00001
11111
00111
00110
00110

样例输出1

10

样例2

样例输入2

3
1 3
3 1
010
101
010

样例输出2

8

样例1解释

应该在 \((1,4)\) 和 \((4,5)\) 之间创建一个传送门。这样做的成本是 \((1-4)^2+(4-5)^2=10\)；

样例2解释

应该在 \((1,3)\) 和 \((3,1)\) 之间创建一个传送门。这样做的成本是 \((1-3)^2+(3-1)^2=8\)。

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(1≤N≤100\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T1\)