题目描述

希蒙这次要做一个能够独立去上学的还孩子，打算坐车去学校。现在希蒙在x1,y1处，学校在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），希蒙只能垂直或水平着在马路上行进。希蒙为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？

输入格式

第1行：一个数 n

第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）

第n+2行：四个数 x1,y1,x2,y2

输出格式

只有1行：最短到达目的地距离

样例

样例输入

3
001
101
100
1 1 3 3

样例输出

4

数据范围与提示

• 对于100% 的数据，$1 \le n,m \le 1000$