Alice 生活在一个平坦的星球上,可以将其建模为大小为 $$$n \times n$$$ 的方形网格,行和列从 $$$1$$$ 到 $$$n$$$ 枚举。我们用有序对 $$$(r, c)$$$ 表示行 $$$r$$$ 和列 $$$c$$$ 交叉处的单元格。网格中的每个单元格要么是陆地,要么是水。
$$$n = 5$$$ 的行星示例。它也出现在第一个样本测试中。
Alice 居住在陆地单元 $$$(r_1, c_1)$$$。她希望前往陆地单元 $$$(r_2, c_2)$$$。她可以随时移动到与她所在位置相邻的单元格之一 - 沿四个方向(即上、下、左或右)之一。
不幸的是,爱丽丝不会游泳,除了步行之外没有可行的交通方式(即她只能在陆地上行走)。结果,爱丽丝的旅行可能无法完成。
为了帮助 Alice,您计划在两个陆地单元之间创建至多一条隧道。隧道将允许 Alice 在两个端点之间自由移动。事实上,创建隧道需要付出很大的努力:在单元 $$$(r_s, c_s)$$$ 和 $$$(r_t, c_t)$$$ 之间创建隧道的成本为 $$$(r_s-r_t)^2 + (c_s-c_t)^2$$$。
目前,您的任务是找到创建最多一条隧道的最低可能成本,以便 Alice 可以从 $$$(r_1, c_1)$$$ 前往 $$$(r_2, c_2)$$$。如果不需要创建隧道,则成本为$$$0$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 方形网格的宽度。
第二行包含两个空格分隔的整数 $$$r_1$$$ 和 $$$c_1$$$ ($$$1 \leq r_1, c_1 \leq n$$$) — 表示 Alice 所在的单元格。
第三行包含两个空格分隔的整数 $$$r_2$$$ 和 $$$c_2$$$ ($$$1 \leq r_2, c_2 \leq n$$$) — 表示 Alice 希望前往的单元格。
以下 $$$n$$$ 行均包含 $$$n$$$ 个字符的字符串。如果 $$$(i, j)$$$ 是陆地,则第 $$$i$$$ 行 ($$$1 \leq i, j \leq n$$$) 的第 $$$j$$$ 个字符为 0;如果 $$$(i, j)$$$ 为水,则第 $$$j$$$ 字符为 1。
保证 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ 是土地。
输出
打印一个整数,该整数是创建至多一条隧道的最小可能成本,以便 Alice 可以从 $$$(r_1, c_1)$$$ 旅行到 $$$(r_2, c_2)$$$。
示例
输入 #1
5 1 1 5 5 00001 11111 00111 00110 00110
输出 #1
10
输入 #2
3 1 3 3 1 010 101 010
输出 #2
8
注意
在第一个示例中,应在单元 $$$(1, 4)$$$ 和 $$$(4, 5)$$$ 之间创建一条隧道。这样做的成本是 $$$(1-4)^2 + (4-5)^2 = 10$$$,这是最优的。这样,Alice 就可以从 $$$(1, 1)$$$ 步行到 $$$(1, 4)$$$,使用从 $$$(1, 4)$$$ 到 $$$(4, 5)$$$ 的隧道,最后从 $$$(4, 5)$$$ 步行到 $$$(5, 5)$$$。
在第二个示例中,显然需要在单元 $$$(1, 3)$$$ 和 $$$(3, 1)$$$ 之间创建一条隧道。这样做的成本是 $$$(1-3)^2 + (3-1)^2 = 8$$$。