A. 走，我们扫雷去

题目背景¶

你很喜欢玩扫雷。

在游戏“扫雷”中，你面对的是一个由若干方格组成的矩阵，每个方格中可能有一颗地雷，也可能没有地雷。

你的基本操作名叫“点开”。每一次，你可以选择一个格子并“点开”它，如果它是地雷，那么你的分数会被扣掉一些，如果它不是地雷，那么你会获得一分，并且会有一个数字显现在方格上，这个数字代表着周围的的八个方格（上、下、左、右、左上、左下、右上、右下）中一共有多少颗地雷（数字为 0 到 8）。如果点开的方格中的数字为 0（这代表这个方格周围的八个方格都不是地雷），那么它周围的方格也会被自动“点开”（这个过程可以递归，也即，如果新的方格中的数字也是 0，那么它周围的八个方格也会被自动“点开”。我们称其为“间接点开”，相对应的，被玩家直接点开的格子称为“直接点开”）。当玩家主动退出，或者时间耗尽后，游戏结束。

请注意，本题的扫雷与标准的扫雷有一些区别：

• 在标准的扫雷中，点开一个包含地雷的方格后，游戏会立刻失败
• 当玩家程序点开所有非地雷方格后，游戏不会自动结束，需要玩家程序主动退出。
• 每次“点开”一个包含数字 0 的格子时，你的程序会收到点开的格子所在的连通块中的所有数字为 0 的格子以及边缘那些数字不为 0 的格子，哪怕这些格子已经被点开过。这个在后文有具体的描述。

下面是 KDE 桌面系统中的“扫雷”游戏的例子（红色的小旗子代表这个方格中有地雷，空白的格子表示格子中的数字为 0）：

经过夜以继日的练习后，高级版扫雷的 $30 \times 16$ 的地图规模对你来说已经是小菜一碟。于是，你决定玩点刺激的。比如，$65536 \times 65535$ 的扫雷？

当然，如此大规模的扫雷肯定不能手工完成。于是，你打算把毕生所学融入到一个程序中，让这个程序来自动化地扫雷。

题目描述¶

你需要写一个（可能是并行的）程序，与我们提供的扫雷 game server 交互。

你可以使用下列库函数来与 game server 交互：

• void minesweeper_init(int &N, int &K, int &constant_A); 在程序开始前，请调用此函数来初始化程序。这个函数会把地图的边长 $N$ 存放在变量 N 中，把地图中的雷的数量 $K$ 存放在变量 K 中，将评分参数 $A$（详见下文）存放在变量 constant_A 中。

• Channel create_channel(void); 请使用此函数创建一个用于和 game server 通信的 Channel 对象。保证不同的 Channel 之间互不干扰，但若有两个进程 / 线程同时操作同一个 Channel，那么大概率会出错。所以建议为每个进程 / 线程单独开一个 Channel。

您可以使用此函数创建至多 1024 个 Channel，不过我建议您尽量保证活跃（反复调用 click()）的 Channel 不超过 8 个。毕竟对于每个您创建的 Channel，game server 中都有一个独立的线程负责处理该 Channel 中的请求。我们在评测的时候仅提供 16 个核心（注：没有超线程），故如果活跃的 Channel 超过 8 个，那么将发生频繁的 context switch，进而在很大程度上影响性能。

• ClickResult Channel::click(int r, int c, bool skip_when_reopen); 这是 Channel 的成员函数，代表“点开 $(r, c)$ 位置所对应的格子”这一操作，$0 \le r, c < n$，返回点开的结果。

ClickResult 类的定义以及成员变量详见 minesweeper_helpers.h。

每次“点开”一个包含数字 0 的格子时，你的程序会收到点开的格子所在的连通块中的所有数字为 0 的格子以及边缘那些数字不为 0 的格子，哪怕这些格子已经被点开过。举个例子：假设棋盘如下（X 代表地雷，左上角坐标为 $(0, 0)$，右上角坐标为 $(0, 2)$，右下角坐标为 $(2, 2)$）：

0 1 X
1 2 1
X 1 0

那么在调用 click(0, 0, false) 时，点开的格子包含 $(0, 0), (0, 1), (1, 0), (1, 1)$；接下来若调用 click(2, 2, false)，那么点开的格子包含 $(1, 1), (1, 2), (2, 1), (2, 2)$。请注意在两次调用中，$(1, 1)$ 这个格子都被点开了。对应到程序中，即为 $(1, 1)$ 这个点在两次 click() 返回的 ClickResult 的 open_grid_pos 数组中均出现了。

如果 skip_when_open 为 true，那么如果这个 $(r, c)$ 这个格子之前就被点开过（不论是被本 Channel 还是其他 Channel 点开，也不论是被直接点开还是被间接点开），那么 click 函数会立刻返回一个 is_skipped=true 的 ClickResult（注：提供本操作的主要目的是节约时间）。请注意，该选项保证如果返回 is_skipped=true，那么 $(r, c)$ 这个格子之前一定被点开过；但是，如果两个线程近似同时点开了同一个格子（或者二者互相间接点开了对方的格子），那么有一定概率两者都没有 skip。换句话说，这里存在一些 data race 的问题。

本函数的复杂度为：$\Theta({\small\text{点开的格子的数量}})$。如果 skip_when_open=true 且该格子之前就被点开，或者格子中含有雷，那么该函数的复杂度为 $\Theta(1)$。

• ClickResult Channel::click_do_not_expand(int r, int c); 这是 Channel 的成员函数，代表“点开 $(r, c)$ 位置所对应的格子，并且不要间接点开”这一操作。

与上面的 click() 函数不同的是，这个函数不会做间接点开。换句话说，假设 $(r, c)$ 这个格子中的数字是 $0$，且周围格子中的数字都不是 $0$，那么 click(r, c) 会点开并返回 $(r, c)$ 以及其周围的格子，而 click_do_not_expand(r, c) 只会点开并返回 $(r, c)$ 这一个格子。

本函数复杂度恒为 $\Theta(1)$。

（注：出题人写完标程之后发现，这个函数好像比上面那个 click() 更常用…）

这些函数均定义在了 minesweeper_helpers.h 中。你可以在程序开头加入 #include "minesweeper_helpers.h" 以使用这些函数。

程序示例¶

为了方便您编程，我们提供了示例程序 naive.cpp 与 interact.cpp。naive.cpp 会使用单个线程依次点开 $N \times N$ 方阵中的每个格子，interact.cpp 是一个交互式的扫雷客户端，在启动后您可以在控制台中输入您想点开的格子的坐标，来“手玩”。

如何准备、测试与提交¶

由于使用了 futex，本题仅支持 linux 系统。建议没有 linux 系统的同学使用 比赛提供的 code server（也可以使用虚拟机或 docker）来运行并调试程序。

准备步骤如下：

• （如果你没有用 code server）安装必要的包，包括 make, gcc, g++, zip
• 下载附加文件 minesweeper_handout.zip，解压缩，并进入解压缩后的文件夹
• 执行 make
• 执行 python3 generate_example_maps.py。该程序会调用 map_generator，在 map/ 目录下生成边长从 16 到 65536 不等的地图文件。地图文件的命名规则为 N_K_seed.map，其中 N 代表地图边长，K 代表地图中的雷的个数，seed 代表随机数种子。生成的地图文件与最终测试时的地图文件均满足 $K = N^2/8$。请注意最终评测时的地图文件的随机数种子并不是 0。

接下来您就可以开始编辑 answer.cpp 了。（注：您在 answer.cpp 中可以使用 #include "lib/csapp.h" 来使用 csapp.h 文件。对应的 csapp.o 将会在链接时自动加入）

如何测试：make && ./judger answer <地图文件，比如 map/16_32_0.map> [时间限制，单位为秒]

如何提交：将 answer.cpp 提交至网站即可。

偷偷说一句，naive.cpp 可以通过前 8 分。

评分标准¶

有若干个测试点，每个测试点的分数为：

$\frac{选手在限定时间内点开的（不同的）非雷格子数 - A \cdot (选手点开的（不同的）雷的个数 - K\cdot0.0002)}{(N^2-K)\times 0.9998} \times 100$，（对 0 取 max，对 100 取 min），其中 $N$ 是地图的边长，$K$ 是地图中雷的总数，$A$ 是常数，详见下方“测试点方案”。

换句话说：即使你有 $0.02\%$ 的非雷格子没有点开，并且不小心点开了 $0.02\%$ 的雷，最后也能满分。（不要怕，这很简单！）

题目总分为所有测试点的分数之和。

硬件配置¶

您的程序将与 game_server 和 judger 一起运行在我们的计算节点上。计算节点的配置为：

• CPU: Intel® Xeon® Platinum 8358 Processor。我们会在您的程序运行时提供 16 个核心，但请注意，每个您创建的 Channel，game server 中都有一个独立的线程负责处理该 Channel 中的请求。如果活跃的 Channel 超过 8 个，那么将发生频繁的 context switch，进而在很大程度上影响性能。所以我们建议活跃的 Channel 数量不要超过八个。
• 内存：64 GB。game_server 与 judger 加起来大约会占用 5 GB 内存，操作系统大约会占用 1 GB 内存，剩下的随便用。

测试点描述¶

如果以上数据点都是满分，那么最终再奖励 10 分。满分 200 分。

附件¶

初始工作区

下载 minesweeper_handout.zip