P16388 [IATI 2024] Puzzle
题目描述
Alice 非常喜欢解数独之类的谜题。最近她发现了一个新谜题。该谜题在一个矩形网格上进行。一些格子初始时填有从 1 到 8（包含 8）的数字；这些格子是“岛屿”。其余格子为空。没有两个岛屿相邻（即没有两个岛屿共享一条边）。目标是在岛屿之间画出一系列桥来连接所有岛屿。这些桥必须满足以下条件：
- 它们必须始于且终于不同的岛屿，并在其间沿直线延伸。
- 它们只能沿正交方向延伸（即不能沿对角线方向）。
- 它们不得与其他任何桥或岛屿交叉。
- 一对岛屿之间最多有两座桥。
- 连接到每个岛屿的桥的数量必须与该岛屿上的数字相符。
- 桥必须将所有岛屿连接成一个单一的连通组。
注意，解可能不唯一。下方左侧是此谜题的一个示例实例，右侧是其一种解（未显示网格）：
:::align{center}
 
:::
Alice 希望在求解各种尺寸的此类谜题时获得帮助。请通过实现一个程序来帮助她。显然，在最坏情况下这个问题可能没有快速的解法，因此重点关注“现实”案例非常重要。为此，你会得到一组测试数据，这组测试数据等同于评测系统中的测试数据（以相同方式生成，参数相同，只是随机种子不同）。
每个测试将包含一个或多个子测试——每个子测试是谜题的一个实例。你的程序将与一个评测器一同编译，该评测器会一个接一个地向程序输入这些子测试，并在你的程序生成了错误解，或你的程序决定停止，或在你的程序完成子测试之前超过时间限制时停止。你在该测试中的得分将与你成功解决的子测试的数量成比例。
### 实现细节
首先，评测器会调用你的函数 $\verb|init|$，以指定测试中的子测试数量以及时间限制（以秒计）（不同的测试可能有不同的时间限制）：
```cpp
void init(int numSubtests, double timeLimit);
```
然后，对于每个子测试，它会用谜题的一个实例来调用你的函数 $\verb|solve|$，该谜题实例表示为一个向量的向量的形式（内层向量表示行），其中空格子用 0 表示。你的函数必须修改这一结构以写出它的解。必须为水平单桥放置 $\verb|-1|$，为水平双桥放置 $\verb|-3|$，为垂直单桥放置 $\verb|-2|$，为垂直双桥放置 $\verb|-4|$。如果它想要解决当前子测试并继续，必须返回 $\verb|true|$；如果它想要停止（即不解决当前子测试），则返回 $\verb|false|$。函数签名如下：
```cpp
bool solve(std::vector& puzzle);
```
最后，你的函数可以调用以下由评测器实现的函数，该函数返回已经过的时间（以秒计）：
```cpp
double timePassed();
```
你的代码必须实现 $\verb|init|$ 和 $\verb|solve|$。除此之外，它可以包含任何其他辅助函数、变量、结构体等。但是，代码不能包含 $\verb|main|$ 函数，并且必须包含头文件 $\verb|puzzle.h|$。
### 本地测试
提供给您的文件包括 $\verb|Lgrader.cpp|$ 和 $\verb|puzzle.h|$，你可以将它们与你的代码一起编译来进行测试。另外还会提供一组具有代表性的样例测试。
输入格式
无
输出格式
无
说明/提示
### 样例交互
首先，调用 $\verb|init(1, 2);|$。然后：
```cpp
solve({
{ 0, 0, 2, 0, 3, 0, 3},
{ 4, 0, 0, 0, 0, 2, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 6, 0, 0, 0, 0, 2, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 4, 0, 0, 0, 0, 0, 4}
});
```
此函数运行，返回 $\verb|true|$ 并将给定的向量修改为如下形式：
```cpp
{
{ 0, 0, 2, -3, 3, -1, 3},
{ 4, -3, -3, -3, -3, 2, -4},
{-4, 0, 0, 0, 0, 0, -4},
{ 6, -3, -3, -3, -3, 2, -4},
{-4, 0, 0, 0, 0, 0, -4},
{-4, 0, 0, 0, 0, 0, -4},
{ 4, -3, -3, -3, -3, -3, 4}
}
```
如果在规定的时间限制内运行，这将为该测试获得满分。
### 约束条件
- $2 \leq \mathrm{numRows}, \mathrm{numColumns} \leq 47$
- $2 \leq \mathrm{numIslands} \leq 200$
### 数据范围
| **测试点编号** | **$\mathrm{numIslands}$** | **$\mathrm{numRows}, \mathrm{numColumns}$** | **$\mathrm{numSubtests}$** | **$\mathrm{timeLimit}$** |
| :---: | :---: | :---: | :---: | :---: |
| $1$–$3$ | $\leq 15$ | $\leq 7$ | $= 1$ | $2$ |
| $4$–$6$ | $\leq 15$ | $\leq 7$ | $= 2$ | $2$ |
| $7$–$8$ | $\leq 100$ | $\leq 31$ | $= 1$ | $2$ |
| $9$–$10$ | $\leq 100$ | $\leq 31$ | $= 6$ | $2$ |
| $11$–$12$ | $\leq 100$ | $\leq 31$ | $= 36$ | $2$ |
| $13$–$14$ | $\leq 200$ | $\leq 47$ | $= 1$ | $5$ |
| $15$–$16$ | $\leq 200$ | $\leq 47$ | $= 6$ | $5$ |
| $17$–$18$ | $\leq 200$ | $\leq 47$ | $= 24$ | $8$ |
所有测试独立计分且分值相同。
### 计分
评测器将反复用谜题实例调用 $\verb|solve|$。如果发生以下任一情况，它将停止调用并终止程序：
- 在你的函数返回之前超过了该测试的时间限制。
- 你的函数返回了一个无效的解。
- 你的函数决定停止（即返回 $\verb|false|$）。
然后，你仍将获得在此之前所有已正确解决的子测试的分数，即如果你解决了 $C$ 个子测试，总共有 $T$ 个子测试，你将获得测试分数中的 $C / T$ 部分。
请注意，你仍需避免触发评测系统 10 秒的硬时间限制。你可以使用 $\verb|timePassed()|$ 并通过返回 $\verb|false|$ 来停止以避免此情况。如果你的程序超出了该限制，它将被终止并获得 0 分。
翻译由 DeepSeek V4 Pro 完成