OI Wiki 交互题实战指南：交互协议、常见评测错误与五道经典例题深度解析-编程实验室

OI Wiki 交互题实战指南：交互协议、常见评测错误与五道经典例题深度解析

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

交互题是算法竞赛中一种要求选手程序与评测程序实时通信的题型：选手程序向评测程序发出询问，并依据反馈逐步逼近答案。本文以 OI Wiki 的交互题专题文档（docs/contest/interaction.md）为骨架，结合仓库中关于题型分类与输入输出优化的配套文档，系统讲解交互题的两种交互方式、评测结果判定规则、缓冲区刷新的关键陷阱、调试手段，并逐题剖析 Bear and Prime 100、Interactive LowerBound、APIO2016 Gap、New Year and Finding Roots、太空站之谜五道经典例题及其完整参考代码，帮助读者从"会写交互代码"进阶到"能在交互次数限制内稳定 AC"。

一、交互题：背景、定位与学习建议

交互题并非新题型——上个世纪的 IOI 就已涉及。虽然交互题在相当长一段时间内未出现在省选以下的比赛中，但 2019 年 NOI 系列比赛中连续出现两道交互题：《P5208[WC2019]I 君的商店》与《P5473[NOI2019]I 君的探险》，这可能代表着交互题重新回到 NOI 系列比赛中。因此，掌握交互题对参加 NOI 系列赛事的选手具有现实意义。

交互题有着鲜明的特点：

前置算法要求不高：交互题一般没有很高的前置算法门槛，通常也没有严格的时间限制。
核心约束是交互次数：程序的优秀程度往往仅取决于交互次数限制，而非运行速度或常数优化。
适合锻炼算法思维：如果只想学习算法本身，交互题未必是最佳载体；但若想有意识地锻炼算法思维，完成交互题是很不错的方法。
建议循序渐进：虽然交互题对选手已掌握算法的要求通常较低，但仍建议掌握一定提高和省选算法后再尝试做交互题，因为此时算法思维水平和知识面已达到一定水准，更容易体会到交互题的精妙之处。

基础的交互题题型介绍可参见 OI Wiki 的题型介绍 - 交互题。

二、两种交互方式：STDIO 交互与 Grader 交互

根据 docs/contest/problems.md 的说明，交互题在技术实现上主要分为两种方式。虽然技术上有不小的差异，但在考察算法的本质上二者没有实际区别。

STDIO 交互（标准 I/O 交互）

STDIO 交互是 Codeforces、AtCoder 等在线平台的交互手段，也是 ICPC 系列赛事中的标准。这类题目中，选手只需像往常一样将询问写到标准输出，刷新输出缓冲后从标准输入读取结果。

关键点在于：选手程序刷新输出缓冲后，通过管道连接它的测评程序（交互器）才能立刻接收到数据。在 C/C++ 中，fflush(stdout)和std::cout << std::flush可以实现这个操作；使用std::cout << std::endl换行时也会自动刷新缓冲区，但是std::cout << '\n'不会；Pascal 则使用flush(output)。

STDIO 交互的一个明显优势在于它可以支持任何编程语言，但输入输出的耗时容易成为问题设计的瓶颈，有时导致评测系统无法区分程序的时间效率差别。

Grader 交互

Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事（特别是 CMS 平台的竞赛）。这类题目中，选手只需编写一个特定的函数完成某项任务，通过调用题目给定的若干辅助函数来进行交互。为了便于选手在本地测试，题目会下发一个头文件与一个参考测评程序grader.cpp（对于 Pascal 语言是一个库graderlib），选手将自己的程序与grader.cpp一同编译方可得到可执行文件：

g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2 ./my_solution # 执行程序

编译得到的程序表现与传统题程序类似：它会打开固定的文件，以固定的格式读取数据，调用选手编写的函数，并将结果和若干信息（例如询问的次数、答案正确性）显示在标准输出上。实际测评时，选手的程序会与一个不同的grader.cpp编译，这个版本一般将所有全局符号设为static，防止选手通过命名冲突的方式破解，任何尝试突破 grader 限制的行为都会被判失格（disqualification）。

Grader 交互由于函数调用开销不大，常常可以允许 $10^6$ 数量级的询问次数，但语言的限制是其短板。如果自己设计题目或举办比赛，需要对两种交互方式认真权衡。

三、交互题的特殊评测结果与常见错误

交互题的错误形态与普通传统题不同，OI Wiki 的交互题文档专门总结了三种特殊的评测结果：

1. Idleness limit exceeded（ILE）

选手每一次输出后都需要刷新缓冲区，否则会引起Idleness limit exceeded错误。这一错误的本质是：交互器在等待选手程序的输出，而选手程序的输出仍滞留在缓冲区中没有被刷新。

另外需要特别注意：如果题目含多组数据，并且程序可以在未读入所有数据前就知道答案，也仍然要读入所有数据，否则会因为读入混乱引起 ILE。一种可行的策略是一次提出多次询问、一次接收所有询问的回答。同时，尽量不要使用快读——快读基于getchar/fread等底层的缓冲机制，容易与交互流程产生冲突，反而引发读取混乱。

2. Wrong Answer（WA）与 Protocol Limit Exceeded（PLE）

如果程序查询次数过多，在 Codeforces 上会给出 Wrong Answer 的评测结果（不过评测系统会说明 Wrong Answer 的原因），而 UVa 会给出Protocol Limit Exceeded (PLE)的评测结果。

3. Protocol Violation（PV）

如果程序交互格式错误，UVa 会给出Protocol Violation (PV)的评测结果。这意味着选手的输出不符合题目约定的交互协议格式。

小结：交互题的两种典型失败模式

失败类型	触发原因	对应平台判定
ILE	输出后未刷新缓冲区 / 未读入全部数据	Idleness limit exceeded
查询次数超限	询问次数超过题目限制	Codeforces: WA；UVa: PLE
交互格式错误	输出格式不符合协议	UVa: PV

四、I/O 封装：交互题的工程化基础

由于交互题输入输出较为繁琐，OI Wiki 建议分别封装输入和输出函数。这样做一方面保证每次输出后刷新缓冲区这一关键动作不被遗漏，另一方面让代码逻辑更清晰、更易排查错误。

这里需要特别强调刷新缓冲区与 I/O 优化的冲突关系。在 docs/contest/io.md 中介绍了std::ios::sync_with_stdio(false)与std::cin.tie(nullptr)两个常用优化，但文档同时警告：在同时进行上述两个操作后，程序中必须手动flush才能确保每次std::cout展现的内容可以在std::cin前出现——因为此时调用std::cin时std::cout不会自动刷新缓冲区。这与交互题的 ILE 错误直接相关：交互题中使用优化后的流式 I/O 时，必须在每次询问输出后显式刷新（std::flush或std::endl），否则交互器将永远等不到选手的询问。

此外，OI Wiki 在交互题文档中明确建议"尽量不要使用快读"。仓库 docs/contest/code/io/io_1.cpp 中的getchar/putchar式快读、docs/contest/code/io/io_2.cpp 中的fread/fwrite式快读，其核心思路都是将字符流缓存在程序侧手动处理；在交互场景中，这类底层字符读取与 printf/scanf 混用极易破坏交互协议的同步性，因此交互题更推荐朴素的printf/scanf（或std::cout/std::cin+ 显式 flush）并做好函数封装。

五、交互题的调试：grader、checker 与静态查错

比赛时如果出题人给出了 grader 头文件（用于 grader 交互题的调试）或者 checker 程序（用于 stdio 交互题的调试），交互题的调试会比较简单，因为交互题的对拍会比普通题目的对拍困难很多。

从工程角度看，交互题的调试成本相当可观：没有testlib.h的情况下，交互细节较多的题目的 stdio 交互库一般有 3k 代码量，再加上 3k 长度的对拍器，至少需要一小时实现。但无论是否有调试程序，调试交互题的代码都往往需要选手模拟与程序的交互过程。因此，交互题对选手的要求是：

能设计出高质量的程序，尽量保证一遍做对；
拥有较强的静态查错能力，在无法运行时定位逻辑错误。

六、例题精讲

1. CF679A Bear and Prime 100

题意：交互器隐藏一个 $[2,100]$ 内的整数，选手最多询问 20 次"该数是否被某个数整除"，判断其是质数还是合数。

思路分析：每个质数都有且只有两个因数，所以直接枚举要猜的数的因数即可。由于限制最多询问 20 次，并且对于较大的数（如 92）尝试分解质因数时发现需要最多枚举到 $\lfloor\frac{n}{2}\rfloor$ 的质数，所以我们先筛出 50 以内的质数，每次把所有这些数都询问一遍。

关键细节：本题对拍比较容易，可以直接把值域内的数都尝试一遍。此时会发现程序无法有效处理质数的平方——例如 4 只能被 2 整除，若只询问 2、3、5、7 等质数，无法区分 $4$ 与质数 $2$ 的倍数特征。因此我们要把 $2,3,5,7$ 的平方 $4,9,25,49$ 都放进去，总共 19 个数字，符合 20 次询问限制。一旦出现两个"是"的回答（例如 $4$ 被 $2$ 和 $4$ 都整除），即可判定为合数。

参考代码（完整代码来自 docs/contest/interaction.md）：

#include <cstdio> constexpr int prime[] = {2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49}; int cnt = 0; char res[5]; int main() { for (int i : prime) { printf("%d\n", i); fflush(stdout); scanf("%s", res); if (res[0] == 'y' && ++cnt == 2) return printf("composite"), 0; } printf("prime"); return 0; }

注意代码中每次printf后紧跟fflush(stdout)，这正是交互题输出铁律的体现。

2. CF843B Interactive LowerBound

题意：给定一个长度为 $n$（$n \le 5 \times 10^4$）的单向链表，已知首元素下标start，元素值严格递增。选手每次可询问一个下标，得到该下标的元素值及其后继下标，最多询问 1999 次，求链表中第一个值不小于 $x$ 的元素。

思路分析：链表最多有 $5 \times 10^4$ 个元素，但只能询问 1999 次，并且只能获取元素的后一个元素，所以普通的遍历整个链表的方法不可用。直接设法逼近目标元素的位置只有一种方法：随机撒点。

对于 $n < 2000$ 的情况直接枚举：依次询问每个下标，取所有值不小于 $x$ 的元素中的最小值。
对于 $n \ge 2000$ 的情况，直接撒 1000 个点。由于元素值严格递增，这些点之间的期望距离很小，可以从小于 $x$ 的最大值开始向后遍历——可以证明在到达下一个撒点之前我们就已得到答案。遍历过程中一旦找到大于等于 $x$ 的元素，就可以直接推出答案。

虽然整体思路简单，但实际情况下，如果没有学习过模拟退火等非完美随机算法，思考起来可能会困难一些。

关键细节——随机种子：由于 Codeforces 具有 hack 机制，很多人会刻意卡掉没有初始化随机种子的代码，所以在random_shuffle()函数前需要srand((size_t)new char)——用动态分配的内存地址作为随机种子，每次运行都不同，无法被 hack 预测。

参考代码：

#include <algorithm> #include <cstdio> #include <cstdlib> constexpr int N = 50005; int n, start, x; int a[N]; int main() { scanf("%d%d%d", &n, &start, &x); if (n < 2000) { int ans = 2e9; for (int i = 1; i <= n; i++) { printf("? %d\n", i), fflush(stdout); int val, next; scanf("%d%d", &val, &next); if (val >= x) ans = std::min(ans, val); } if (ans == 2e9) ans = -1; printf("! %d", ans), fflush(stdout); } else { srand((size_t) new char); int p = start, ans = 0; for (int i = 1; i <= n; i++) a[i] = i; std::random_shuffle(a + 1, a + n + 1); for (int i = 1; i <= 1000; i++) { printf("? %d\n", a[i]), fflush(stdout); int val, next; scanf("%d%d", &val, &next); if (val < x && val > ans) p = a[i], ans = val; } while (p != -1 && ans < x) { printf("? %d\n", p), fflush(stdout); int val, next; scanf("%d%d", &val, &next); ans = val; p = next; } if (ans < x) ans = -1; printf("! %d", ans), fflush(stdout); } return 0; }

本代码展示了一个交互题的完整流程骨架：?为询问指令、!为回答指令，每次输出后立即fflush(stdout)。

3. UOJ206 [APIO2016] Gap

题意：有 $N$ 个严格递增的非负整数 $a_1, a_2, \cdots, a_N$（$0 \le a_1 < a_2 < \cdots < a_N \le 10^{18}$），选手不能直接读入序列，但可以通过 grader 提供的MinMax(s, t, &mn, &mx)函数查询区间 $[s,t]$ 内的最小值和最大值（若区间内无数则返回 -1）。求相邻两数差的最大值。本题分两个子任务，分别考察不同的查询限制。

子任务 1：查询次数限制

查询次数限制刚好为 $\frac{N+1}{2}$。因为一开始不知道任何数，所以需要先询问范围 $[1, 10^{18}]$ 获得全局最大最小值。之后考虑怎么每一次都能获取之前没有获取过的值，从而在次数范围内获取序列内的所有数——方法很简单：每次查询 $[s, t]$ 后，设获得的值为 $mn, mx$，则下一次查询 $[mn + 1, mx - 1]$。这样每次查询都恰好取到一对新数（左右两端各一个），$\frac{N+1}{2}$ 次查询正好取完所有 $N$ 个数。

子任务 2：询问区间大小限制

子任务 2 要求询问区间内的数的数量之和不能超过 $3N$，所以要最小化询问区间。子任务 1 的方法不再可用，因为其询问区间内的数数量之和规模为 $O(N^2)$。可以考虑二分值域，但这种方法并不可靠，最坏可能被卡到 $O(N^2)$。我们需要更有效的划分值域的方法，避免查询区间内的点重复查询、浪费机会。

考虑到答案不会小于 $\lfloor\frac{a_n - a_1}{N - 1}\rfloor$（这是相邻差值的理论下界），所以可以按这个值划分值域：设 $i$ 初始为 0，$ans$ 初始为上述值，每次询问 $[i, i + ans]$ 并更新 $ans$（用取到的相邻差值更新），之后再以 $ans$ 为步长让 $i$ 自增。这种方法避免了重复查询，总询问区间内的数数量满足限制。

不过这种方法也不能很好地适用于子任务 1，因为最坏情况下很多询问的值域内可能一个数都没有。

参考代码（Grader 交互风格，包含"gap.h"头文件）：

#include <algorithm> #include <cstdio> #include "gap.h" long long findGap(int T, int N) { static long long a[100005] = {}, ans = 0; long long s = 0, t = 1e18, s1, t1; if (T == 1) { int l = 1, r = N; while (l <= r) { MinMax(s, t, &s1, &t1); a[l++] = s1, a[r--] = t1; s = s1 + 1, t = t1 - 1; } for (int i = 2; i <= N; i++) ans = std::max(ans, a[i] - a[i - 1]); } else if (T == 2) { MinMax(s, t, &s1, &t1); ans = (t1 - s1) / (N - 1); long long l = s1 + 1, r = t1, last = s1; for (long long i = l; i <= r;) { MinMax(i, i + ans, &s1, &t1); i += ans + 1; if (s1 != -1) ans = std::max(ans, s1 - last), last = t1; } } return ans; }

4. CF750F New Year and Finding Roots

题意：给定一棵完全二叉树（高度 $h \le 7$，共 $2^h - 1$ 个节点，节点编号未知），选手每次询问一个节点，交互器返回其邻居数量 $k$（$1 \le k \le 3$）及所有邻居编号。需要在最多 16 次询问内找到根节点。

思路分析：$h \le 7$、询问次数 $\le 16$ 的严格要求，要求我们非常严格地最大化利用每次访问获得的信息。

$h \le 4$ 时可以直接暴力枚举。
随机撒点不是好方法：随机撒点无法确定自己是否足够接近根节点，且单纯随机撒点至少有一次碰到根节点的概率为 $1 - \left(\frac{2^h - 2}{2^h - 1}\right)$，即使排除重复撒点的情况后，碰到根节点的概率仍然非常小。

由于 $1 \le k \le 3$，并且我们并不知道哪一边更接近根节点，所以考虑最坏情况：如果 $k = 3$ 时，前两次遍历方向都是远离根节点的，第三次遍历方向是接近根节点的，所以必须往三个方向都遍历。

考虑 bfs 和 dfs 两种遍历方法：由于 bfs 搜索树可能很大，优先考虑 dfs。当然，如果知道当前深度，并且当前深度小到深度范围内的搜索树规模小于等于剩余次数，就可以直接 bfs。

关键洞察——如何确定方向与深度：知道当前节点的深度以及当前遍历方向会获得很大优势，然而"当前在往根节点还是往叶子节点遍历"是非常难判断的。如果使用 dfs，只有当遍历到根节点（$k = 2$）或者叶子节点（$k = 1$）时才知道当前方向。所以需要尽可能知道当前节点深度，且不能采用类似迭代加深搜索的方法在遍历中途停下来。

考虑随机一个初始节点，从初始节点出发可能碰到最坏情况：

如果 $k = 1$，就可以直接知道当前节点的深度（是叶子）；
如果 $k = 2$，当前节点即根节点；
如果 $k = 3$，直接考虑往三个方向 dfs。其中两个方向是直接往叶子节点的方向，遍历路径长度相同；另一个方向是往根节点的方向，不过可能中途不小心往叶子节点方向走了，遍历路径长度会较大。此时就可以计算出当前节点的深度。

当 $k = 1$ 或 $k = 3$ 时，需要考虑较长的遍历路径。可以知道路径上深度最小的点（必定比初始节点深度小）。如果为访问过的节点打标记、不再遍历，此时从该节点开始就只有一条遍历路径。虽然这条路径可能还是会走向叶子节点，但是这条路径上同样必然存在深度比起点小的节点，就可以从这个节点开始继续重复上面的步骤。

最坏情况分析：考虑 $h = 7$ 的最坏情况（每次只往根节点走一步就直接往叶子节点走），如果只 dfs，最坏需要 $\frac{(1 + 7) \times 7}{2} = 28$ 次询问。不过已经知道初始节点的深度，所以可以算出所有已遍历节点的深度，并判断是否可以从深度最小的点直接 bfs。

此时可以算出最坏需要 17 次，还差 1 次。于是考虑从搜索树上去掉一个节点：当进行深度为 $k$ 的 bfs 时，搜索树节点最坏有 $2^k - 1$ 个，可能需要 $2^k - 1$ 次询问才能确定哪个节点的邻居恰有 2 个；但如果已经对其中 $2^k - 2$ 个节点询问后，可以知道最后一个节点肯定是根节点。

此时最坏情况下的最优解为：$h = 7$ 时，从叶子节点 dfs，每次都是只往根节点走一步就直接往叶子节点走，询问 10 次后，当前已知最小深度的节点深度为 4。由于已知其父亲，直接从其父亲开始 bfs（搜索树深度为 3，节点数为 $2^3 - 1 = 7$）。在 bfs 时询问了 $2^3 - 2 = 6$ 次后，确定 bfs 搜索树上最后一个节点为根节点。此时算法可以刚好卡到最坏 16 次。

参考代码：

#include <algorithm> #include <cstdio> #include <queue> #include <vector> using namespace std; constexpr int N = 256 + 5; int T, h, chance; bool ok; vector<int> to[N], path; bool read(int x) { if (to[x].empty()) { printf("? %d\n", x), fflush(stdout); int k, t; scanf("%d", &k); if (k == 0) exit(0); for (int i = 0; i < k; i++) { scanf("%d", &t); to[x].push_back(t); } if (k == 2) { printf("! %d\n", x), fflush(stdout); return ok = true; } chance--; } return false; } bool dfs(int x) { if (to[x].empty()) path.push_back(x); if (read(x)) return true; for (int i : to[x]) if (to[i].empty()) return dfs(i); return false; } void bfs(int s, int k) { queue<int> q; for (int i : to[s]) if (to[i].empty()) q.push(i); for (int i = 1; i < k; i++) { int x = q.front(); q.pop(); if (read(x)) return; for (int j : to[x]) if (to[j].empty()) q.push(j); } for (int i = 1; i < k; i++) { int x = q.front(); q.pop(); if (read(x)) return; } printf("! %d\n", q.front()), fflush(stdout); } int main() { for (scanf("%d", &T); T--;) { ok = false; for (int i = 0; i < N; i++) to[i].clear(); chance = 16; scanf("%d", &h); if (h == 0) exit(0); vector<int> long_path; if (read(1)) continue; int root, dep; if (to[1].size() == 1) root = 1, dep = h; else { for (int i : to[1]) { path.clear(); if (dfs(i)) break; if (path.size() > long_path.size()) swap(path, long_path); } if (ok) continue; dep = h - (path.size() + long_path.size()) / 2; root = long_path.at((long_path.size() - (h - dep)) - 1); } while ((1 << (dep - 1)) - 2 > chance) { path.clear(); if (dfs(root)) break; dep = h - (h - dep + path.size()) / 2; root = path.at((path.size() - (h - dep)) - 1); } if (!ok) bfs(root, 1 << (dep - 2)); } return 0; }

注意代码中的chance变量在每次read（真实询问）时递减，配合while循环条件(1 << (dep - 1)) - 2 > chance动态判断"当前剩余次数是否足够直接 bfs"，正是"把询问次数当作一等公民资源来管理"的体现。

5. UVa12731 太空站之谜 Mysterious Space Station

题意：在一个 $n \times m$ 的地图上，选手需要远程操控一个机器人探索未知区域，找出所有传送门的位置及其配对关系。机器人的唯一反馈是移动时是否撞墙。

思路分析：由于唯一的反馈是移动时是否撞墙，所以应该考虑在机器人不走丢的情况下，尽量接近墙边走路。这样做有两个好处：

靠近墙边走路时，很容易知道自己会不会撞墙，获取到尽量多的信息；
墙边都是不会出现传送门的格子，可以避免机器人走丢。

单手扶墙法：如果已知机器人可能在墙边的某个位置，要确定机器人是否真的在这个位置，就可以通过单手扶墙法确定自己是否真的在这个位置。根据拓扑学原理，在两边都是墙的迷宫中，如果从入口进入，并且总是用一只手扶着同一边墙，就可以保证找到出口。由于本题中的墙是闭合的，所以只需要沿着墙边的道路走，就可以保证回到原点而不会撞墙。另外，由于墙边的道路是地图上的最大闭合回路，实际代码中并不需要特意撞墙以保证机器人在墙边，可以使用标记在地图中标明墙边道路（参考代码中的Path状态）。而且一旦撞了墙，就需要赶快沿着原路返回，可以在避免机器人走丢的同时减少步数。

由此可以推断出确定机器人是否在特定格子的试错法：将机器人从不走到未知格子或已知传送门的情况下走到墙边的道路上，然后绕着墙边道路走一圈。这个过程中如果没有撞墙，就可以确定机器人确实在特定格子。

算法流程：

初始化：一开始标出图中所有未知格子（Unknown），将所有与墙相邻的格子标记为墙边道路（Path），并预计算出墙边回路的行走路径。
找出传送门：从上到下、从左到右依次判断每个未知格子是否是传送门。可以先走到未知格子上方，然后向下、向左走，再用上面的试错法判断机器人是不是在未知格子的左侧。如果不是，说明机器人不在应该在的位置，即该未知格子是传送门，并将其周围 8 个方向的相邻未知格子标记为普通空地（Space）。
配对传送门：找出 $2k$ 个未知格子后，需要判断配对关系。实际方法很简单——直接暴力配对。由于 $k \le 5$，最多只需要 $9 + 7 + 5 + 3$ 次试错法（每对一组的代价递减）。作为对比，判断图中全部未知格子的情况最多需要 $121 - 40$ 次试错法。
回答：将 $k$ 组配对输出。

关于代码的可用性说明：OI Wiki 文档特别注明，下面的代码只能通过 UOJ 的镜像题《#247.【Rujia Liu's Present 7】Mysterious Space Station》，而无法通过 UVa 原题——修改了 UOJ 上刘汝佳的标程后仍无法通过 UVa 原题，并且暂时无法联系到刘汝佳，所以代码以 UOJ 为准。同时文档指出，刘汝佳的标程质量比下面这份代码高很多，同一份数据下标程使用的移动次数非常少。

参考代码：

#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <stack> #define Wall 0 #define Unknown 1 #define Space 2 #define Gate 3 #define Path 4 const int N = 20; const int dir[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}}; const char dirs[5] = "ESWN"; int n, m, k; int a[N][N], id[N][N]; struct point { int x, y; point(int x = 0, int y = 0) : x(x), y(y) {} bool operator==(const point& tmp) const { return x == tmp.x && y == tmp.y; } bool operator!=(const point& tmp) const { return !(*this == tmp); } point side(int d) const { return point(x + dir[d][0], y + dir[d][1]); } int check(int d) { return a[x + dir[d][0]][y + dir[d][1]]; } int id() { return ::id[x][y]; } } start; std::vector<std::pair<point, int>> path; std::pair<point, point> ans[N]; std::pair<point, bool> vis[N]; bool walk(int d) { printf("MoveRobot %c\n", dirs[d]); fflush(stdout); int ret; scanf("%d", &ret); return ret; } bool walk(int d, std::stack<int>& st) { if (walk(d)) { st.push(d); return true; } return false; } bool read() { if (scanf("%d%d%d", &n, &m, &k) != 3) return false; if (n == 0) return false; memset(a, 0, sizeof(a)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { char c; std::cin >> c; if (c == 'S') start = point(i, j); if (c == '*') a[i][j] = Wall; else a[i][j] = Unknown; } return true; } void answer() { for (int i = 0; i < k; i++) printf("Answer %d %d\n", ans[i].first.id(), ans[i].second.id()); fflush(stdout); } // 单手扶墙法，因为靠墙的 Path 是极大闭合环，所以只需要在沿着 Path // 走的过程中没有碰到障碍就可以了 void wall_follower_init(point x, int last, int wallside, point s) { if (x == s && !path.empty()) return; if (x.check(wallside) == Path) { path.push_back(std::make_pair(x, wallside)); wall_follower_init(x.side(wallside), wallside, last ^ 2, s); } else if (x.check(last) == Wall) { for (int i = 0; i < 4; i++) if (i != (last ^ 2) && x.check(i) != Wall) { path.push_back(std::make_pair(x, i)); wall_follower_init(x.side(i), i, last, s); return; } } else { path.push_back(std::make_pair(x, last)); wall_follower_init(x.side(last), last, wallside, s); } } void init() { int cnt = 1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (a[i][j] == Unknown) { id[i][j] = cnt++; for (int k = 0; k < 8; k++) if (point(i, j).check(k) == Wall) { a[i][j] = Path; break; } } else id[i][j] = 0; } path.clear(); int wallside = 0, last = 0; for (int i = 0; i < 4; i++) if (start.check(i) == Wall) { wallside = i; break; } for (int i = 0; i < 4; i++) if (start.check(i) == Path && i != (wallside ^ 2)) { last = i; break; } wall_follower_init(start, last, wallside, start); } void undo(std::stack<int>& st) { while (!st.empty()) walk(st.top() ^ 2), st.pop(); } bool wall_follower(point x) { std::stack<int> st; bool ok = true; int i = 0; while (i < path.size() && path[i].first != x) i++; for (int j = i; ok && j < path.size(); j++) { if (walk(path[j].second)) st.push(path[j].second); else ok = false; } for (int j = 0; ok && j < i; j++) { if (walk(path[j].second)) st.push(path[j].second); else ok = false; } if (!ok) undo(st); return ok; } // 确定自己当前在 // x，使用「摸着石头过河」的方法，只需要沿着可以避开障碍、未知格子和传送门的方向走到 // Path 就行． 在找传送门和配对传送门时使用 void bfs(point s, point t, std::vector<int>& v) { static int map[N][N] = {}; memset(map, -1, sizeof(map)); std::queue<point> q; map[s.x][s.y] = 4; q.push(s); while (!q.empty()) { point x = q.front(); q.pop(); if (x == t) break; for (int i = 0; i < 4; i++) { point y = x.side(i); if ((x.check(i) == Path || x.check(i) == Space) && map[y.x][y.y] == -1) { map[y.x][y.y] = i; q.push(y); } } } for (point x = t; x != s; x = x.side(map[x.x][x.y] ^ 2)) { v.push_back(map[x.x][x.y]); } std::reverse(v.begin(), v.end()); } bool move(point s, point t, std::stack<int>& st) { // 在靠近传送门时使用 static std::vector<int> v; v.clear(); bfs(s, t, v); for (int i : v) if (!walk(i, st)) return false; return true; } // 尽可能快地向墙边移动 bool make_sure(point x, int last) { if (a[x.x][x.y] == Path) return wall_follower(x); for (int i = 0; i < 4; i++) if ((x.check(i) == Path || x.check(i) == Space) && i != (last ^ 2)) { if (!walk(i)) return false; bool ret = make_sure(x.side(i), i); walk(i ^ 2); return ret; } return false; } void find_gate() { int cnt = 0; std::stack<int> st; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (cnt == k * 2 && a[i][j] == Unknown) a[i][j] = Space; else if (a[i][j] == Unknown) { bool ok = true; if (!move(start, point(i - 1, j), st)) ok = false; else if (!walk(1, st)) ok = false; else if (!walk(2, st)) ok = false; else if (!make_sure(point(i, j - 1), -1)) ok = false; if (!ok) { vis[cnt++] = std::make_pair(point(i, j), false); a[i][j] = Gate; for (int k = 0; k < 8; k++) { point y = point(i, j).side(k); if (point(i, j).check(k) == Unknown) a[y.x][y.y] = Space; } } else a[i][j] = Space; undo(st); } } void make_gate_pair() { int cnt = 0; std::stack<int> st; for (int i = 0; i < k * 2; i++) if (!vis[i].second) for (int j = 0; !vis[i].second && j < k * 2; j++) if (j != i && !vis[j].second) { bool ok = true; if (!move(start, vis[i].first.side(2), st)) ok = false; else if (!walk(0, st)) ok = false; else if (!make_sure(vis[j].first.side(0), -1)) ok = false; if (ok) { ans[cnt++] = std::make_pair(vis[i].first, vis[j].first); vis[i].second = vis[j].second = true; } undo(st); } } int main() { while (read()) { init(); find_gate(); make_gate_pair(); answer(); } return 0; }

这道题的参考代码体现了交互题中几个重要的工程技巧：将地图状态用Wall / Unknown / Space / Gate / Path五种标记显式建模；用undo()配合栈实现"撞墙后沿原路返回"；所有输出（MoveRobot、Answer）都紧跟fflush(stdout)。

七、习题推荐与拓展阅读

OI Wiki 的交互题文档推荐的进阶练习：

刘汝佳的交互题专场比赛 Rujia Liu's Present 7：质量非常高，推荐一做（包含前文的太空站之谜）。
P5473[NOI2019]I 君的探险：2019 年 NOI 交互题，考察随机化与图论结合的能力。
P5208[WC2019]I 君的商店：2019 年 WC 交互题，考察二分与询问策略设计。

关于交互题评测原理的延伸阅读，OI Wiki 文档推荐了"用 Linux 管道实现 online judge 的交互题功能"的思路——本质上，STDIO 交互题就是评测系统通过管道将选手程序与交互器程序的标准输入输出连接起来，选手输出的询问经管道送入交互器，交互器的应答再经管道送回选手程序的标准输入。理解了这一数据流模型，就能更好地把握"每次输出后必须刷新缓冲区"这条铁律背后的原因。