题目描述

兔子挖出了一个隧道系统，共有 $N$ 层（自上而下编号为 $0$ 到 $N-1$）。每一层有 $M$ 个房间（自左到右编号为 $0$ 到 $M-1$）。

可以把这些房间看成一个 $N \times M$ 的网格。任意两个上下或左右相邻的房间之间都有隧道。整个系统下方还有一个巨大的藏宝室，可以看作第 $N$ 层，并且它与第 $N-1$ 层的所有房间都有垂直隧道相连。

但是，其中一些房间已经坍塌，因此这些房间以及与之相连的所有隧道都不可通过。

为了保护宝藏，兔子在几乎所有的竖直隧道上都设置了陷阱。更精确地说：

• 对于每一层（包括藏宝室所在的第 $N$ 层），恰好有一条进入该层的竖直隧道是安全的；
• 并且保证存在一条从地表到藏宝室的安全路径（即路径上没有经过任何带陷阱的竖直隧道）。

Alice 想安全到达兔子的藏宝室。

她已经通过声呐知道哪些房间是坍塌的，但仍然不知道哪些竖直隧道安全，哪些有陷阱。她还观察到兔子总是很匆忙，因此它总会走一条最短的安全路径从地表进入隧道系统到达宝藏（或者反向离开），也就是那条不重复房间的唯一安全路径。

Alice 看到兔子是从地表上方的第 $K$ 号房间进入第 $0$ 层的，因此她也可以安全地从这里进入系统。

此外，Alice 带了一只猎犬，可以通过气味判断兔子是否经过某个房间。她可以在当前层到达某个房间并进行一次调查，判断兔子是否经过这里。经过若干次调查之后，当她能够确定某个竖直隧道是安全的时，她就可以从该房间向下进入下一层。

Alice 希望在保证绝对安全的前提下，用最少的最坏情况下调查次数到达藏宝室。

形式化地，对于给定测试数据（$N,M,K$ 以及坍塌房间集合），我们定义一个探索策略的最坏调查次数如下：

• 枚举所有可能的安全竖直隧道配置；
• 对每种配置计算兔子的路径，并独立运行你的策略；
• 若你的策略在所有情况下都能安全到达藏宝室，则最坏调查次数定义为这些情况下调查次数的最大值；
• 否则，认为该策略的最坏调查次数为无穷大。

再在所有合法策略中取最小值，得到该测试的允许最大调查次数。

你需要编写程序，在不穿过坍塌房间、不经过有陷阱隧道的前提下，到达藏宝室，并保证所用调查次数不超过该测试数据允许的最优最坏次数。

实现方式

你需要实现如下函数：

void solve(int n, int m, int k, const std::vector<std::vector<bool>>& blocked)

它会对每个测试点调用一次，参数含义如下：

• n：层数 $N$
• m：每层房间数 $M$
• k：Alice 初始进入的第 $0$ 层房间编号
• blocked[level][position]：表示该房间是否坍塌

你需要在该函数中完成探索过程。起点是第 $0$ 层的第 $K$ 个房间，目标是到达第 $N$ 层的藏宝室。

在 solve 以及你自己编写的辅助函数中，你可以调用以下两个函数：

1. 调查某个房间

bool investigate(int s)

表示前往当前层的第 s 个房间（它必须可达，即中途不能经过坍塌房间），并检查兔子是否经过该房间。

• 若兔子经过，返回 true
• 否则返回 false

2. 进入下一层

void goDeeper(int s)

表示前往当前层的第 s 个房间（必须可达），并通过该房间的竖直隧道进入下一层。

要求：

• 这条竖直隧道必须是安全的；
• 下一层对应位置的房间不能坍塌。

如果已经到达第 $N$ 层，则 solve 应直接返回。

交互说明

• 你的程序会和评测器一起编译；
• 不要实现 main 函数；
• 不要读写标准输入输出；
• 需要包含头文件：

#include "tunnels.h"

评测器有时可能是自适应但确定性的，也就是说，它可以根据你之前的操作动态决定 investigate 的返回值或 goDeeper 是否成功，但仍保证这一切与某种合法的安全隧道配置相符。

如果你尝试通过一条有陷阱的竖直隧道，或者评测器判断你已经不可能在允许的调查次数内完成任务，则可能直接终止程序。

评测器运行时间不计入时间限制。

本地测试

提供了本地 grader 和头文件。

本地 grader：

• 不是自适应的；
• 不进行复杂验证；
• 读取 $N,M,K$ 和一个由 0/1 组成的房间矩阵（无空格）；
• 调用你的 solve；
• 当你调用 investigate 或 goDeeper 时，输出相应信息；
• 对于 investigate，它会额外读入一个 0 或 1 作为返回值。

你可以自由修改本地 grader。

数据范围

• $1 \le N, M \le 5000$

子任务

子任务	分值	限制
1	5	$M=2$
2	16	没有坍塌房间
3	19	$N,M \le 100$
4		$N,M \le 400$
5	20	$N,M \le 1000$
6	21	无额外限制

只有通过某个子任务及其依赖的全部测试，才能获得该子任务分数。

样例（本地交互格式）

输入

2 3 1
001
100

交互过程

solve(2, 3, 1, {{0, 0, 1}, {1, 0, 0}})
goDeeper(1)
investigate(2): return true
goDeeper(2)

该测试数据的最优最坏调查次数为 $1$，所以上述策略可以通过此样例。