问题 3261 --冰岛(iceland)

3261: 冰岛(iceland)

时间限制: 1 Sec  内存限制: 256 MB
提交: 3  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

假设你在一个 n × n 的冰面上,并且你想到达这个冰面的某处,可是由于冰面太滑 了,所以当你向某个方向出发后,你没有办法使自己停下来直到你碰到了某个障碍物—— 因为你可以抓住障碍物使得你的身体停止运动。 因为你已经知道了整个地图,所以你决定在行动之前先计算出最快可到达目标的路线,使得你可以不用走太多冤枉路,这时你决定编程解决这个问题…… 

输入

第一行包括一个正整数 n(n ≤ 1000) 

以下 n 行,每行包括 n 个数字 0 1,0 表示该点为空地可以滑行,1 表示该点为障 碍物(障碍物无法穿过)。保证最外圈的地形为障碍物,也就是你无法离开这个地图。 接下来 1 行包括 2 个整数 x, y(1 ≤ x, y ≤ n),表示一开始你处于坐标 (x, y) 再接下来1行包括2个整数 x2, y2(1 ≤ x2, y2 ≤ 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
样例2
4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
2 2
3 3

样例输出

样例1
2
样例2
impossible

提示


数据约束和子任务



 20% 数据满足 n ≤ 5



 40% 数据满足 n ≤ 10 



 60% 数据满足 n ≤ 200 



100%数据满足n<=1000

来源

[提交][状态]