SP9 DIRVS - Direct Visibility

建设 GSM 网络是一个非常昂贵且复杂的任务。此外，在基站（Base Transceiver Stations，BTS）建成并投入运行之后，我们需要进行多种测量以确定网络状态，并提出有效的改进建议。 ACM 的技术人员有一套专用设备，用来测量电磁场强度、收发器的功率和信号质量。该设备被装在一个巨大的背包中，技术人员必须带着它从一个 BTS 移动到另一个。不幸的是，背包没有足够的存储空间来保存所有测量值。它只有一个小型缓存，只能保存几秒钟的数据。然后必须通过红外连接（IRDA）将这些数值传输到 BTS。IRDA 需要技术人员可以直接看到 BTS。 你的任务是找到两个相邻 BTS 之间的一条路径，使得始终至少有其中一个 BTS 可以被看到。

输入第一行包含一个正整数 $T$（约为 $500$）。它表示随后测试用例的数量。每个测试用例由一个城镇描述组成。为简单起见，城镇被建模为 $P \times Q$ 的矩形网格，每个格子正好宽 $1$ 米。对于每个格子，给出一个非负整数 $Z _ {i,j}$，表示该处地形的高度，单位为米。这意味着城镇模型由一系列立方体构成，每个立方体要么为实心，要么为空。不存在“半实心”立方体。 每个测试用例的第一行包含两个整数 $P$ 和 $Q$，用单个空格分隔，$1 \le P, Q \le 200$。接下来有 $P$ 行，每行包含 $Q$ 个用空格分隔的整数。这些数就是 $Z _ {i, j}$，其中 $1 \le i \le P$，$1 \le j \le Q$，且 $0 \le Z _ {i, j} \le 5000$。地形描述之后，每个测试用例的最后一行有四个数字 $R _ 1, C _ 1, R _ 2, C _ 2$。这些数字表示两个 BTS 的位置，$1 \le R _ 1, R _ 2 \le P$，$1 \le C _ 1, C _ 2 \le Q$。第一个坐标（$R$）表示行，第二个坐标表示列。 技术人员以步为单位移动（步代表标准技术人员的基本位置移动）。每步都在两个相邻格子之间进行，方向仅限北、南、东或西，不能对角移动。仅当 $B$ 格子的地形高度与 $A$ 格子的地形高度差不大时，才能从 $A$ 步行至 $B$。技术人员在一步中最多可以向上攀登 $1$ 米，或向下下降 $3$ 米。 在每一步结束时，必须至少能看见两个 BTS 中的一个。然而，在“步”的过程中间可能存在某个点看不见任何 BTS，这种情况允许，由缓存处理。若在 BTS 坐标处地形上方的单位立方体与技术人员所在格子上方的单位立方体之间具有直接可见性，则认为该 BTS 可见。两个立方体之间的直接可见性意味着连接它们中心点的直线不会穿过任何实心立方体，但该直线可以接触任意数量的实心立方体。换言之，视 BTS 和技术人员为分别位于地面正上方半米处、位于格子中心的点。 注意，IRDA 光束可以穿过两个仅在棱边相接的立方体之间，尽管它们之间没有空间。这是因为光束触及它们，但并不穿过它们中的任何一个。请参见样例输入的最后一个测试用例，以了解此类情况的示例。

你需要找出满足上述条件的、从在 $(R _ 1, C _ 1)$ 的 BTS 到在 $(R _ 2, C _ 2)$ 的 BTS 的最短路径。所有移动必须在相邻格子之间进行，地形高度变化不能过大，并且每一步结束时至少要有一个 BTS 可见。 对于每个测试用例，输出一行，内容为 $\texttt{The shortest path is }M\texttt{ steps long.}$，其中 $M$ 是所需的步数。如果不存在这样的路径，则输出 $\texttt{Mission impossible!}$。