题目描述

Alice 很喜欢解各种谜题，例如数独等。最近她发现了一种新的谜题。

这个谜题在一个矩形网格上进行。某些格子中一开始写有 1 到 8 之间的数字，这些格子称为“岛屿”；其余格子为空。

保证任意两个岛屿都不会相邻，也就是说，不存在共享边的两个岛屿。

目标是通过画若干座桥，将所有岛屿连接起来。桥必须满足以下条件：

• 每座桥必须连接两个不同的岛屿，中间沿直线延伸；
• 桥只能沿上下或左右方向延伸，不能斜着画；
• 桥不能穿过任何其他桥，也不能穿过任何岛屿；
• 任意一对岛屿之间最多连接两座桥；
• 每个岛屿连接到的桥的总数，必须恰好等于该岛屿上的数字；
• 所有桥连起来之后，所有岛屿必须属于同一个连通块。

注意：一个谜题的解不一定唯一。

Alice 想让你帮助她解决若干个不同规模的此类谜题。显然，这个问题在最坏情况下不一定存在很快的算法，因此评测重点放在“现实风格”的测试数据上。

为此，题目提供了一组测试，其生成方式、参数范围与正式评测相同，只是随机种子不同。每个测试由一个或多个子测试组成，每个子测试对应一个谜题实例。

你的程序将与评测器一起编译。评测器会依次把这些子测试送给你的程序；一旦发生以下任一情况，评测就会停止：

• 你的程序输出了错误解；
• 你的程序主动停止；
• 在你完成当前子测试之前，该测试的时间限制已经到达。

你的得分与成功解决的子测试数量成正比。

实现要求

首先，评测器会调用如下函数，告知本次测试的子测试数量和时间限制（不同测试的时间限制可能不同）：

void init(int numSubtests, double timeLimit);

随后，对每个子测试，评测器会调用：

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

其中 puzzle 表示当前谜题：

• 它是一个二维数组，内层数组表示行；
• 空格子用 0 表示；
• 岛屿格子用 1..8 表示。

你的函数需要直接修改这个二维数组，写入一组合法解。桥的表示方式如下：

• -1：水平单桥；
• -3：水平双桥；
• -2：竖直单桥；
• -4：竖直双桥。

函数返回值含义如下：

• 返回 true：表示你愿意继续求解当前子测试，并继续后续子测试；
• 返回 false：表示你选择停止，不再求解当前子测试及后续子测试。

评测器还提供如下函数：

double timePassed();

它返回当前已用时间（单位：秒）。

代码要求

你的程序必须：

• 实现 init 和 solve；
• 不能包含 main 函数；
• 必须包含头文件：

#include "puzzle.h"

除此之外，你可以自行定义任意辅助函数、变量、结构体等。

本地测试

题目提供 Lgrader.cpp 与 puzzle.h，你可以将它们与你的程序一起编译进行本地测试。

同时还提供了一组具有代表性的样例测试数据。

约束条件

• 2 <= numRows, numColumns <= 47
• 2 <= numIslands <= 200

测试点

测试编号	numIslands	numRows, numColumns	numSubtests	timeLimit
1-3	<= 15	<= 7	= 1	2
4-6			= 2
7-8	<= 100	<= 31	= 1
9-10			= 6
11-12			= 36
13-14	<= 200	<= 47	= 1	5
15-16			= 6
17-18			= 24	8

所有测试相互独立，分值相同。

评分规则

评测器会反复调用 solve 处理谜题实例。当出现以下任一情况时，会立即停止继续调用并结束程序：

• 测试的时间限制在你的函数返回前已经到达；
• 你的函数返回了非法解；
• 你的函数决定停止（即返回 false）。

如果如此停止，那么在此之前所有已经正确解决的子测试仍然计分。也就是说：

• 若你正确解决了 C 个子测试；
• 总共有 T 个子测试；

那么你在该测试上的得分比例为 C / T。

注意：你仍然必须避免超过评测系统的硬时间限制 10 秒。你可以通过 timePassed() 监控时间，并在合适时返回 false 来提前停止。

如果你的程序超过硬时间限制，将被直接终止，并得到 0 分。

样例通信

首先会调用：

init(1, 2.0);

随后评测器调用：

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}
});

你的函数运行后，返回 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}
}

若它在给定时间限制内完成，则该测试可获得满分。