题目描述

构建GSM网络是一项非常昂贵且复杂的任务。此外，在基站收发台（BTS）建成并运行后，我们需要进行各种测量以确定网络状态，并提出有效的改进措施。

ACM的技术人员有一种特殊设备，用于测量电磁场强度、收发器的功率和信号质量。该设备装在一个巨大的背包中，技术人员必须携带它从一个BTS移动到另一个BTS。不幸的是，背包的内存不足以存储所有测量值。它只有一个小缓存，可以存储几秒钟的数据。然后，这些数据必须通过红外连接（IRDA）传输到BTS。IRDA需要技术人员和BTS之间的直接视线。

你的任务是找到两个相邻BTS之间的路径，使得在每一步结束时至少有一个BTS始终可见。

输入格式

输入的第一行是一个正整数$T$，表示测试用例的数量。每个测试用例包含一个城镇描述。为简化问题，城镇被建模为一个$P \times Q$的矩形网格，每个网格是一个边长为1米的正方形。对于每个网格，给出一个非负整数$Z_{i,j}$，表示该位置的地形高度（单位：米）。这意味着城镇模型由立方体组成，每个立方体要么是实心的，要么是空心的。不存在“半实心”立方体。

每个测试用例的第一行包含两个整数$P$和$Q$，用空格分隔，满足$1 \leq P, Q \leq 200$。接下来是$P$行，每行包含$Q$个用空格分隔的整数，表示$Z_{i,j}$，其中$1 \leq i \leq P$，$1 \leq j \leq Q$，且$0 \leq Z_{i,j} \leq 5000$。在地形描述之后，每个测试用例的最后一行包含四个整数$R1, C1, R2, C2$，表示两个BTS的位置，满足$1 \leq R1, R2 \leq P$，$1 \leq C1, C2 \leq Q$。第一个坐标（$R$）表示城镇的行号，第二个坐标（$C$）表示列号。

技术人员的移动以步为单位（步表示“标准技术员基本位置移动”）。每一步在两个相邻的正方形网格之间进行，即只能向北、南、西或东方向移动，不能对角线移动。从网格$A$到网格$B$的移动（从$A$到$B$的步）仅在网格$B$的地形高度与网格$A$的高度相差不大时允许。技术人员在一步中最多可以爬升1米或下降3米。

在每一步结束时，至少有一个BTS必须可见。然而，在“移动过程中”可能存在某些点没有BTS可见，这是允许的，因为数据会被缓存处理。BTS被视为可见的条件是：在BTS坐标的正上方（即地形上方0.5米处）的立方体中心与技术人员所在网格正上方的立方体中心之间存在直接视线。直接视线是指连接两个立方体中心的直线不与任何实心立方体相交，但可以接触任意数量的实心立方体。换句话说，假设BTS和技术人员都是位于各自网格正上方0.5米处的点。

注意，IRDA光束可以通过两个立方体的边缘接触处，即使它们之间没有空隙。这是因为这种光束接触了这两个立方体，但并未与其中任何一个相交。示例输入的最后一个测试用例展示了这种情况。

输出格式

你需要找到满足上述条件的最短路径。所有移动必须在相邻网格之间进行，地形高度变化不能过大，且每一步结束时至少有一个BTS可见。

对于每个测试用例，输出一行： • 如果存在这样的路径，输出：The shortest path is M steps long.，其中$M$是所需步数。

• 如果不存在这样的路径，输出：Mission impossible!。

示例输入

4
5 5
8 7 6 5 4
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 2 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 5 5 1
6 12
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 9 5 5 5 5 5 5 5
5 9 1 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
6 1 3 12

示例输出

The shortest path is 10 steps long.
Mission impossible!
The shortest path is 14 steps long.
The shortest path is 18 steps long.

题目来源 Central Europe 2000