题目描述

Alice 非常喜欢解数独之类的谜题。最近她发现了一个新谜题。该谜题在一个矩形网格上进行。一些格子初始时填有从 1 到 8（包含 8）的数字；这些格子是“岛屿”。其余格子为空。没有两个岛屿相邻（即没有两个岛屿共享一条边）。目标是在岛屿之间画出一系列桥来连接所有岛屿。这些桥必须满足以下条件：

• 它们必须始于且终于不同的岛屿，并在其间沿直线延伸。
• 它们只能沿正交方向延伸（即不能沿对角线方向）。
• 它们不得与其他任何桥或岛屿交叉。
• 一对岛屿之间最多有两座桥。
• 连接到每个岛屿的桥的数量必须与该岛屿上的数字相符。
• 桥必须将所有岛屿连接成一个单一的连通组。

注意，解可能不唯一。下方左侧是此谜题的一个示例实例，右侧是其一种解（未显示网格）：

:::align{center} :::

Alice 希望在求解各种尺寸的此类谜题时获得帮助。请通过实现一个程序来帮助她。显然，在最坏情况下这个问题可能没有快速的解法，因此重点关注“现实”案例非常重要。为此，你会得到一组测试数据，这组测试数据等同于评测系统中的测试数据（以相同方式生成，参数相同，只是随机种子不同）。

每个测试将包含一个或多个子测试——每个子测试是谜题的一个实例。你的程序将与一个评测器一同编译，该评测器会一个接一个地向程序输入这些子测试，并在你的程序生成了错误解，或你的程序决定停止，或在你的程序完成子测试之前超过时间限制时停止。你在该测试中的得分将与你成功解决的子测试的数量成比例。

实现细节

首先，评测器会调用你的函数 $\verb|init|$，以指定测试中的子测试数量以及时间限制（以秒计）（不同的测试可能有不同的时间限制）：

void init(int numSubtests, double timeLimit);

然后，对于每个子测试，它会用谜题的一个实例来调用你的函数 $\verb|solve|$，该谜题实例表示为一个向量的向量的形式（内层向量表示行），其中空格子用 0 表示。你的函数必须修改这一结构以写出它的解。必须为水平单桥放置 $\verb|-1|$，为水平双桥放置 $\verb|-3|$，为垂直单桥放置 $\verb|-2|$，为垂直双桥放置 $\verb|-4|$。如果它想要解决当前子测试并继续，必须返回 $\verb|true|$；如果它想要停止（即不解决当前子测试），则返回 $\verb|false|$。函数签名如下：

bool solve(std::vector<std::vector<int>>& puzzle);

最后，你的函数可以调用以下由评测器实现的函数，该函数返回已经过的时间（以秒计）：

double timePassed();

你的代码必须实现 $\verb|init|$ 和 $\verb|solve|$。除此之外，它可以包含任何其他辅助函数、变量、结构体等。但是，代码不能包含 $\verb|main|$ 函数，并且必须包含头文件 $\verb|puzzle.h|$。

本地测试

提供给您的文件包括 $\verb|Lgrader.cpp|$ 和 $\verb|puzzle.h|$，你可以将它们与你的代码一起编译来进行测试。另外还会提供一组具有代表性的样例测试。

提示

样例交互

首先，调用 $\verb|init(1, 2);|$。然后：

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|$ 并将给定的向量修改为如下形式：

{
    { 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$

数据范围

所有测试独立计分且分值相同。

计分

评测器将反复用谜题实例调用 $\verb|solve|$。如果发生以下任一情况，它将停止调用并终止程序：

• 在你的函数返回之前超过了该测试的时间限制。
• 你的函数返回了一个无效的解。
• 你的函数决定停止（即返回 $\verb|false|$）。

然后，你仍将获得在此之前所有已正确解决的子测试的分数，即如果你解决了 $C$ 个子测试，总共有 $T$ 个子测试，你将获得测试分数中的 $C / T$ 部分。

请注意，你仍需避免触发评测系统 10 秒的硬时间限制。你可以使用 $\verb|timePassed()|$ 并通过返回 $\verb|false|$ 来停止以避免此情况。如果你的程序超出了该限制，它将被终止并获得 0 分。

翻译由 DeepSeek V4 Pro 完成