问题 4858 --3.冰上行动

4858: 3.冰上行动

题目描述

  假设你在一个 $n\times n$ 的冰面上，并且你想到达这个冰面的某处，可是由于冰面太滑了，所以当你向某个方向出发后，你没有办法使自己停下来，除非你碰到了某个障碍物。
因为你已经知道了整个地图，所以你决定在行动之前先计算出最快可到达目标的时间。

输入

第一行包括一个正整数 。
以下 $n$ 行，每行包括 $n$ 个数字（0 或 1），0 表示该点为空地可以滑行，1 表示该点为障碍物（障碍物无法穿过）。保证你无法离开这个地图。
接下来 1 行包括 2 个整数 $x,y$，表示一开始你处于坐标 $(x,y)$。
再接下来 1 行包括 2 个整数 $x_2,y_2$，表示你想要到达的目标为 $(x_2,y_2)$。

输出

能到达目标的最短时间（假设每经过一次滑行需要花费 $1$ 单位的时间，无论这次滑行距离的长短）。
所谓到达目标要求必须停留在  $(x_2,y_2)$，也就是你不能在到达之后被迫滑向下一个点。
当你无法到达目标点时，你只须输出一行字符串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 复制 
4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
2 2
3 3
输出#2 复制 
impossible

提示

对于 $20\%$ 数据，$1 \leq x,y,x_2,y_2 \leq n \leq 5$；
对于 $40\%$ 数据，$1 \leq x,y,x_2,y_2 \leq n \leq 10$；
对于 $60\%$ 数据，$1 \leq x,y,x_2,y_2 \leq n \leq 200$；
对于 $100\%$ 数据，$1 \leq x,y,x_2,y_2 \leq n \leq 1000$。

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
未评定
标签
点击显示
递交数
14
已通过
2
通过率
15%
时间限制
1 秒
内存限制
256 MB
来源
2020CSP入门组模拟4
收藏