题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 x1 , y1 处，车站在 x2 , y2 处。现在给出一个 n * n ( n ≤ 1000 )的地图，0 表示马路，1 表示店铺(不能从店铺穿过)，爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离(每两个相邻坐标间距离为 1 )。你能帮他解决吗?

输入格式

第 1 行：包含一个数 n。（1 $\leq$ n $\leq$ 1000） 。

第 2 行：到第几 +1 行:整个地图描述( 0 表示马路， 1 表示店铺，注意两个数之间没有空格)。

第 n+2 行：四个数 x1 , y1 , x2 , y2，（1 $\leq$ x1 , x2 , y1 , y2 $\leq$ 1000） 。

输出格式

只有 1 行，即最短到达目的地距离。

样例

3
001
101
100
1 1 3 3

4

16
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
0101010101000000
0000000000000000
2 2 16 16

28