P16381 [IATI 2025] Tunnels

兔子挖了一个隧道系统，共有 $N$ 层（从上到下编号为 $0$ 到 $N-1$）。每层有 $M$ 个房间（从左到右编号为 $0$ 到 $M-1$）。我们可以将这些房间视为一个 $N$ 行 $M$ 列网格中的格子。所有相邻（共享一条边）的房间之间都有隧道。在这一切的下方，有一个巨大的宝藏室（实际上横跨整个第 $N$ 层）。宝藏室与第 $N-1$ 层的所有房间之间都有隧道。然而，这 $NM$ 个房间中有一些已经坍塌，因此被阻塞了（与之相连的所有隧道也一并阻塞）。 兔子想要保护他的宝藏，因此他在几乎所有的垂直隧道中都设置了陷阱。更准确地说，每一层（包括宝藏室所在的那一层）**恰好**有一个安全（没有陷阱）的入向垂直隧道。此外，数据保证存在一条从地表到宝藏室的安全路径（即不经过任何陷阱隧道的路径）。 Alice 想要到达兔子的宝藏室，但盲目地进入隧道系统将是极其危险的。首先，她利用声纳研究了这些房间，并查明了哪些房间是阻塞的。然而，她仍然不知道哪些隧道有陷阱，哪些是安全的。接着，她开始观察兔子。她知道兔子总是匆匆忙忙，因此他总是选取从地表到宝藏的最短安全（无陷阱）路径（反之亦然），即那条不重复经过房间的**唯一**安全路径。她还看到兔子从第 $0$ 层、位于地表房间 $K$ 上方进入了隧道系统（$0 \leq K < M$）。这使她也能安全地进入隧道系统。最后，Alice 带来了一只熟悉兔子气味的寻血犬。借助这条狗，她可以前往一个可达的房间（位于她当前所在的层），并对其进行调查——检查兔子是否曾到过那里。经过一系列这样的调查后，当她确定无疑时，她可以前往一个可达的房间，并从那里向下走（到下一层）。她不想拿自己的生命冒险，因此她必须绝对确信所选的垂直隧道是安全的。她希望在**最坏情况下**使用尽可能少的调查次数安全到达宝藏（她也很匆忙，因为她还要参加一个茶会）。 形式化地，对于给定的测试数据（$N$、$M$、$K$ 以及阻塞房间的集合），我们这样定义一种探索策略的**最坏情况调查次数**：枚举所有可能的安全隧道集合，对每一种情况计算兔子的路径，并在每一种这样的情况上（独立地）运行该策略。该策略的最坏情况调查次数是它在所有那些情况中（假设该策略是合法的，并且能在所有情况下安全到达宝藏；否则，我们称其最坏情况调查次数为无穷大）所执行调查次数的最大值。然后，我们再枚举所有可能的策略，并找出最小的可能最坏情况调查次数。这个最小值就是该测试数据允许的最大调查次数。 Alice 是一个聪明的女孩，但兔子的隧道系统太过庞大，以至于连她也无法找出最优的探索策略。请你编写一个程序来帮助她，该程序将探索隧道系统，并在不超过该测试数据允许的调查次数的情况下到达宝藏室，同时不经过阻塞的房间或穿越有陷阱的隧道。（你的程序需要满足所有这些要求，才能正确通过给定的测试数据。） ### 实现细节 你必须实现函数 `solve`： ```cpp void solve(int n, int m, int k, const std::vector& blocked) ``` 对于每个测试数据，该函数会被调用一次，并传入 $N$、$M$ 和 $K$，以及关于各个房间的描述（以 `blocked[level][position]` 为索引）。它必须执行隧道探索（从第 $0$ 层、房间 $K$ 开始），到达宝藏室所在的层（第 $N$ 层），且所用调查次数不超过该测试数据的最小可能最坏情况调查次数。在该函数（以及你编写的其他函数）中，你可以调用 `investigate` 和 `goDeeper` 函数： ```cpp bool investigate(int s) ``` 调用 `investigate` 表示前往当前层编号为 $S$ 的房间（该房间必须是可达的，即途中不能有任何阻塞的房间），并检查兔子在前往宝藏的路上是否会经过这个房间。如果会经过，函数返回 `true`，否则返回 `false`。 ```cpp void goDeeper(int s) ``` 调用 `goDeeper` 表示前往当前层编号为 $S$ 的房间（该房间必须是可达的），然后通过该处的垂直隧道向下走到下一层。该隧道必须是安全的（即没有陷阱），并且下方的房间不能是阻塞的。之后，你将从下一层的房间 $S$ 继续探索（除非你已经到达了第 $N$ 层，此时你的 `solve` 函数应当返回）。 你的代码将会与一个评测器（grader）一起编译，因此不应实现 `main` 函数，也不应从 `stdin` 读取或向 `stdout` 写入任何内容。你还需要包含头文件 `tunnels.h`。 评测器有时可能是自适应的（但仍然是确定性的），也就是说，它可能会根据你的程序之前的行为来决定 `investigate` 返回什么，或 `goDeeper` 是否成功，而并非基于一组固定的安全隧道。然而，数据保证评测器所做的一切都与某组可能的安全隧道相符。如果你调用 `goDeeper` 试图穿越一个有陷阱的隧道，或者评测器认为你的程序已无法在要求的调查次数内解决该测试数据，评测器可能会终止程序。此外，评测器的运行时间不计入时限。 ### 本地测试 为了在本地测试你的程序，我们提供了一个本地评测器和一个头文件。本地评测器不是自适应的，也不进行任何计算或验证。它读入 $N$、$M$、$K$ 以及一个由 0 和 1 组成的矩阵（无空格），然后调用你的 `solve` 函数，并在你的程序调用 `investigate` 或 `goDeeper` 时输出相应信息（每次 `investigate` 调用都需要输入——一个 0 或 1，作为其返回值）。你可以自由修改本地评测器。

无

无

### 样例测试 | **输入** | **交互** | | :--- | :--- | | `2 3 1` | `solve(2, 3, 1, {{0, 0, 1}, {1, 0, 0}})` | | `001` | `goDeeper(1)` | | `100` | `investigate(2): 返回 true` | | | `goDeeper(2)` | ### 数据范围 - $1 \leq N, M \leq 5000$ ### 子任务 | **子任务** | **分数** | **约束条件** | | :---: | :---: | :---: | | $1$ | $5$ | $M = 2$ | | $2$ | $16$ | 没有房间阻塞。 | | $3$ | $19$ | $N, M \leq 100$ | | $4$ | $19$ | $N, M \leq 400$ | | $5$ | $20$ | $N, M \leq 1000$ | | $6$ | $21$ | 无。 | 你只有在正确通过某个子任务内的所有测试数据、以及它所包含的所有其他子任务的测试数据后，才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成