Description

你正划着皮艇穿越一个地下洞穴系统，突然发现潮水正在上涨，你被困住了！幸运的是，你有这片洞穴系统的地图。在潮水开始退去之前，你都无法离开，所以你要在这里待上一段时间。在此期间，你希望能找出潮水开始退去时最快离开洞穴的路线。

洞穴系统是一个 $N \times M$ 的网格。你的地图包含两个 $N \times M$ 的数字网格：一个指定每个格子的天花板高度，另一个指定每个格子的地板高度。洞穴的地板是多孔的，这意味着随着水位下降，水不会停留在水位线以上。

你被困在地图的西北角。当前水位为 $H$ 厘米，一旦开始下降，将以每秒 $10$ 厘米的速度下降，直到降至 $0$。出口位于地图的东南角。现在出口处也被水覆盖，但只要潮水开始下降，它就能被通过。

在任何时刻，你都可以向北、南、东或西移动到相邻的格子，前提是满足以下约束：

• 当前水位、当前格子的地板高度、以及相邻格子的地板高度，三者都必须至少比相邻格子的天花板高度低 $50$ 厘米。注意：这意味着你永远无法进入一个地板与天花板间隙小于 $50$ 厘米的格子。
• 相邻格子的地板高度也必须至少比当前格子的天花板高度低 $50$ 厘米。
• 你永远不能移出地图边界。

需要注意的是，你可以随意上下移动（你划皮艇很有运动天赋！）。例如，你可以从地板高度为 $10$ 厘米的格子移动到相邻的地板高度为 $9000$ 厘米的格子（只要满足上述约束）。

这些约束如下图所示：

• 第一幅图中，你无法向右移动，因为当前水位距离右侧格子的天花板不足 $50$ 厘米。
• 第二幅图中，你无法向右移动，因为当前格子的地板距离右侧格子的天花板不足 $50$ 厘米。
• 第三幅图中，你无法向右移动，因为右侧格子的地板距离其天花板不足 $50$ 厘米。你永远无法从任何方向进入该格子。
• 第四幅图中，你无法向右移动，因为右侧格子的地板距离当前格子的天花板不足 $50$ 厘米。

从一个格子移动到另一个格子时，如果你离开该格子时水面距离地板还有至少 $20$ 厘米，那么移动需要 $1$ 秒（你可以划皮艇）；否则需要 $10$ 秒（你得拖着皮艇走）。注意，所需时间只取决于你离开的格子的水位，而不是你要进入的格子的水位。

在潮水开始退去之前，你可以在洞中随意移动时间，不计入答案。你需要计算的是，从潮水开始下降那一刻起，到你到达出口所需的最短时间。

Input Format

• 第一行包含一个整数 $T$，表示测试用例数。
• 接下来有 $T$ 个测试用例，每个测试用例以一行 $H$、$N$、$M$ 开头，分别表示初始水位（厘米）和地图的行列数。接下来的 $2N$ 行给出天花板和地板高度，具体如下：
  • 接下来 $N$ 行，每行 $M$ 个空格分隔的整数，第 $i$ 行第 $j$ 个数为 $C_{ij}$，表示 $(j, i)$ 位置的天花板高度（厘米），$i$ 坐标向南递增，$j$ 坐标向东递增。
  • 再接下来 $N$ 行，每行 $M$ 个空格分隔的整数，表示地板高度，格式同上。
• 起点处天花板与初始水位之间至少有 $50$ 厘米空气，且天花板与地板之间至少有 $50$ 厘米空间。
• 出口处天花板与地板之间至少有 $50$ 厘米空间。
• 总是存在一条可通向出口的路径（毕竟你能进来！）。

Output Format

对于每个测试用例，输出一行 "Case #x: t"，其中 $x$ 为测试用例编号（从 $1$ 开始），$t$ 为从潮水开始下降到你离开洞穴所需的时间（秒）。只要答案的绝对或相对误差不超过 $10^{-6}$，即视为正确。

有可能你能在潮水下降前就到达出口。在这种情况下，你可以在出口处等潮水开始下降，因此答案应为 $0$（这正是样例的第四组数据）。

4
200 1 2
250 233
180 100
100 3 3
500 500 500
500 500 600
500 140 1000
10 10 10
10 10 490
10 10 10
100 3 3
500 100 500
100 100 500
500 500 500
10 10 10
10 10 10
10 10 10
100 2 2
1000 1000
1000 1000
100 900
900 100

Case #1: 11.7
Case #2: 3.0
Case #3: 18.0
Case #4: 0.0

Hint

样例说明

在第一个样例中，最初东侧格子的天花板与水面仅有 $33$ 厘米距离，所以你必须等水位下降 $1.7$ 秒后才能进入。一旦可以进入，你就可以前进——但此时西侧格子的水面距离地板仅 $3$ 厘米，你必须拖着皮艇走 $10$ 秒才能到达出口。

第二个样例起点条件更好——相邻格子有很大空间，因此你可以在潮水退去前移动到 $(1, 1)$。一旦在那里，你只需等潮水下降到 $90$ 厘米（需 $1$ 秒），然后向南再向东即可离开（共需 $3$ 秒）。注意你无法通过 $(2, 1)$，即使那里的天花板足够高，因为该格子的地板与任何相邻格子的天花板间隙都只有 $10$ 厘米。

第三个样例与第一个类似——你必须在起点等到水位降到 $50$ 厘米，然后才能出发；但三步后水位降到 $20$ 厘米，只高出地板 $10$ 厘米，因此第四步需要拖皮艇走 $10$ 秒。

第四个样例你非常幸运！你可以在潮水下降前就到达出口，在那里等待潮水下降。

测试集 1（18 分，结果可见）

• $1 \leq T \leq 50$
• $1 \leq N, M \leq 10$
• $1 \leq H \leq 1000$
• $1 \leq F_{xy} \leq C_{xy} \leq 1000$

测试集 2（18 分，结果隐藏）

• $1 \leq T \leq 50$
• $1 \leq N, M \leq 100$
• $1 \leq H \leq 10000$
• $1 \leq F_{xy} \leq C_{xy} \leq 10000$

翻译由 ChatGPT-4.1 完成。