题目描述

小蒲在一条商业街上逛了整整一个下午,此刻只想尽快走到地铁站坐车回家。他站在 $(x_1, y_1)$ 的位置,地铁站在 $(x_2, y_2)$ 的位置。整条商业街可以抽象成一张 $n \times n$($n \le 1000$)的方格地图:格子为 $0$ 表示可以通行的路面,格子为 $1$ 表示沿街的商铺(不能穿行)。小蒲每一步只能向上、下、左、右四个方向走到相邻的格子,且相邻两个格子之间的距离都算作 $1$。为了节省体力,小蒲想走最短的路线。请你帮他算出从当前位置到地铁站的最短距离。

输入格式

第 $1$ 行包含一个整数 $n$。

第 $2$ 行到第 $n+1$ 行:地图的具体内容($0$ 表示路面,$1$ 表示商铺;注意同一行的数字之间没有空格)。

第 $n+2$ 行:四个整数 $x_1, y_1, x_2, y_2$。

输出格式

输出一行一个整数,即到达地铁站的最短距离。

样例

3
001
101
100
1 1 3 3

4

提示

对于 $20\%$ 的数据,满足 $1\leq n \le 100$。

对于 $100\%$ 的数据,满足 $1\leq n \le 1000$。

数据保证起点与终点都是路面,且一定可以互相到达。