题目描述

给定一个 N × M 的网格，左上角坐标为 (0,0)。初始时，部分格子中已经放有陷阱。

现在有两个玩家 X 和 Y，以及一个棋子“猎手”。X 总是先手。游戏规则如下：

1. 在第一步，当前行动方需要把猎手放到某个没有陷阱的格子里。
2. 从第二步开始，当前行动方必须把猎手移动到一个 上下左右相邻、并且 没有陷阱 的格子。
3. 每次移动后，猎手原来所在的格子会立刻变成陷阱。
4. 无法行动的玩家判负。

你需要实现函数 play()，与评测程序对弈。你的程序可以自行决定扮演先手还是后手，并尽力保证获胜。

• 如果你能确保击败评测程序，则该测试点得分；
• 否则该测试点得分为 0。

你需要实现的函数

void play(int n, int m, const std::vector<std::vector<char>> &table);

其中：

• n, m 表示棋盘大小；
• table[i][j] == '#' 表示该格初始有陷阱；
• table[i][j] == '.' 表示该格初始为空。

你的源文件开头应包含：

#include "hunter.h"

提交代码中 不要写 main()。

与评测程序的交互方式

评测程序会向你提供如下函数：

std::pair<int, int> makeMove(int i, int j);

你必须通过调用它来完成自己的回合。

含义

• 当你调用 makeMove(i, j) 时，表示你要把猎手移动到 (i, j)。
• 如果该步合法，评测程序会立即执行它自己的下一步，并返回它移动后猎手所在的位置。
• 如果你已经获胜，评测程序会返回 (-1, -1)，此时 play() 应立即结束。
• 如果你走了非法步，或者评测程序获胜，则本测试点记为失败。

特殊约定

如果你希望 让评测程序先手，则在一开始调用：

makeMove(-1, -1);

本题在 Hydro 中的评测方式

这是一个 函数题。Hydro 会自动把你的代码与提供的 grader.cpp、hunter.h 一起编译。

你只需要提交 play() 的实现即可。

数据范围

• 1 ≤ N, M ≤ 100

子任务

1. 10 分：N = 1
2. 20 分：初始棋盘为空（没有任何陷阱）
3. 30 分：N ≤ 10
4. 40 分：无额外限制

只有通过某个子任务中的 全部测试点，才能拿到该子任务的分数。