ROBOTI（COI 2010 T4）题解

题目分析

这是一道交互题，核心场景为：两个机器人在 $R \times C$ 网格中，无法直接获取位置信息，仅能通过每次移动后的曼哈顿距离反馈，将机器人移动到指定的两个 x 目标位置。关键限制与条件：

• 机器人移动失败的情况：目标格被占用、超出网格、被另一个机器人占据；
• 每次操作后仅能获得两机器人的曼哈顿距离，无其他位置信息；
• 网格中未被占用的单元格连通，保证机器人可到达目标位置。

核心思路

1. 位置探测：确定机器人初始位置

由于无法直接获取坐标，代码通过试探性移动 + 距离反馈 实现位置探测：

• test1/test2 函数：分别尝试移动机器人 1/2 向四个方向（U/D/L/R），根据曼哈顿距离是否变化，判断该方向是否可移动（可移动则距离变化，不可移动则距离不变）；
• testb 函数：结合两个机器人的可移动方向反馈，交叉验证并确定机器人 2 的初始位置 bx, by，同时标记机器人 1 的初始位置；
• 最终通过 dfs1/dfs2 遍历网格，基于移动后的距离变化，还原整个网格的可通行/不可通行状态，完成机器人初始位置的定位。

2. 路径规划：BFS 求解最短路径

确定机器人初始位置和网格结构后，使用广度优先搜索（BFS） 规划路径：

• bfs1/bfs2 函数：分别为机器人 1/2 计算从初始位置到目标位置的最短路径，记录父节点信息；
• findans1/findans2 函数：回溯父节点信息，生成移动指令序列；
• shuchu1/shuchu2 函数：输出移动指令，完成机器人到目标位置的移动。

3. 目标匹配：分配机器人到目标位置

由于有两个目标位置 x，代码通过验证可达性，为两个机器人分配合理的目标：

• 依次尝试机器人 1 到第一个/第二个目标、机器人 2 到第二个/第一个目标的组合；
• 选择可达的组合执行路径移动，确保两个机器人最终到达指定位置。

解题步骤

1. 初始化与网格探测

• 读取网格规模和初始布局，初始化探测网格 now 为未知状态（?）；
• 从初始试探位置出发，调用 dfs1 移动机器人 1，根据距离变化标记网格可通行（.）/不可通行（#）；
• 通过 testb 确定机器人 2 的初始位置，再调用 dfs2 完成整个网格的探测。

2. 坐标映射与目标定位

将探测得到的机器人位置映射到原始网格坐标系，定位两个 x 目标位置的坐标。

3. 路径规划与指令执行

• 对每个机器人，使用 BFS 计算到目标位置的最短路径；
• 验证机器人与目标位置的可达性，选择合法的匹配组合；
• 输出移动指令，将机器人移动到目标位置，最后输出 0 结束程序。

复杂度分析

• 位置探测阶段：DFS 遍历网格的时间复杂度为 $O(R \times C)$，每个单元格最多被访问一次，每次移动操作对应一次交互，交互次数与网格规模线性相关；
• 路径规划阶段：BFS 求解最短路径的时间复杂度为 $O(R \times C)$，空间复杂度为 $O(R \times C)$（存储访问标记和父节点信息）；
• 整体复杂度：$O(R \times C)$，适配 $R,C \le 200$ 的数据范围，交互次数在合理限度内。

总结

本题的核心是通过交互反馈反推位置信息，将“不可见”的位置问题转化为“可探测”的网格遍历问题：

1. 利用试探性移动和曼哈顿距离的变化，还原网格结构与机器人初始位置，突破“无位置信息”的限制；
2. 结合 BFS 求解最短路径，保证机器人高效移动到目标位置；
3. 目标匹配逻辑确保两个机器人正确分配到指定位置，完成任务要求。

这种“试探-反馈-建模-规划”的思路是交互题的典型解法，关键在于通过有限的交互信息，构建问题的完整模型，再利用经典算法解决核心任务。