题目描述

假设你在一个$n\times n$的冰面上，并且你想到达这个冰面的某处，可是由于冰面太滑了，所以当你向某个方向出发后，你没有办法使自己停下来直到你碰到了某个障碍物——因为你可以抓住障碍物使得你的身体停止运动。

因为你已经知道了整个地图，所以你决定在行动之前先计算出最快可到达目标的路线，使得你可以不用走太多冤枉路，这时你决定编程解决这个问题……

输入格式

第一行包括一个正整数$n(n \leq 1000)$

以下$n$行，每行包括$n$个数字$（0或1）$，$0$表示该点为空地可以滑行，$1$表示该点为障碍物（障碍物无法穿过）。保证最外圈的地形为障碍物，也就是你无法离开这个地图。

接下来$1$行包括$2$个整数$x,y（1 \leq x,y \leq n）$，表示一开始你处于坐标$(x,y)$

再接下来１行包括２个整数$x2,y2(1 \leq x2,y2 \leq n)$，表示你想要到达的目标为$(x2,y2)$

输出格式

只有一个整数$t$，表示能到达目标的最短时间（假设每经过一次滑行需要花费$1$单位的时间，无论这次滑行距离的长短）。所谓到达目标要求必须停留在$(x2,y2)$，也就是你不能在到达之后被迫滑向下一个点。当你无法到达目标点时，你只须输出一行字符串$impossible$。

样例

样例输入1

5
1 1 1 1 1
1 0 0 1 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
2 2
4 3

样例输出1

2

• 样例说明：由(2,2)到(2,3)，再由(2,3)到(4,3)，2次滑行到达终点

输入样例2

4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
2 2
3 3

输出样例2

impossible

数据范围与提示

• 20%数据满足 $n \leq 5$
• 40%数据满足 $n \leq 10$
• 60%数据满足 $n \leq 200$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$256\mathrm{MB}$

大样例下载