# 恐怖机器人：题解

## 解法比较

出题人解法先按四连通标记障碍组，再在状态 $(x,y,a,c)$ 上做 BFS，其中 $a$ 是上一步移动的轴，$c$ 是拆除的障碍组（也包括不拆除）。每次只能换轴移动，且只有所选组变为可通行。另用允许的连通性检查区分题目规定的两类不可达情况。固定 $c$ 后，状态转移与下文的 BFS 完全相同；单位边长保证第一次到达就是最短路。

出题人实现同时保存所有 $c$ 的距离。若格子数为 $V$ 、障碍组数为 $C$ ，时间、空间上界均为 $O((C+1)V)$ .Codex（GPT-6）采用的实现逐个枚举拆除组，每次复用位置与方向数组，时间上界不变，工作空间降为 $O(V)$ .这是减少同时驻留状态的改进，拆除组枚举和交替方向 BFS 均沿用出题人解法。

## 将追逐写成路径

固定轰炸选择。设要塞的路线为 $v_0,v_1,\ldots,v_t$ ，其中 $v_0$ 是起点、$v_t$ 是第一个到达的陷阱。机器人先放在 $v_1$ .在要塞走到 $v_i$ 前，机器人从 $v_i$ 移向 $v_{i+1}$ ；最后停在 $v_t$ 等待要塞进入。

只使用一个机器人，当且仅当每一对相邻移动 $v_{i-1}\to v_i$ 与 $v_i\to v_{i+1}$ 不在同一直线上。八个方向因此可以合并为四类无向轴：竖直、水平、主对角线、副对角线。相邻两步的轴必须不同。最后一步之后无需再转向，因为捕获已经结束。

## 从全部陷阱反向搜索

状态 $(u,a)$ 表示位于格子 $u$ ，已经走过的一步属于轴 $a$ .从陷阱逆向走回起点时，同样要求相邻两步轴不同。

把每个陷阱的四个状态都以距离 $0$ 入队。这样第一步可以选择任意轴。处理状态 $(u,a)$ 时，枚举可通行相邻格 $v$ ，若连线轴为 $b\ne a$ ，则转移至 $(v,b)$ ，距离加一。用多源 BFS 求最短路；一个起点的四种状态距离的最小值，就是此轰炸选择下一个机器人所需的最少移动次数。

从陷阱初始化全部轴并不要求真的执行一步。它只编码“第一步没有方向限制”。任何从陷阱开始的非空路径都能选一个与首步不同的初始轴。

## 多个机器人和不可达

允许不断补充机器人时，每条可通行的八连通路径都能实现：每次把一个机器人放在下一格，再让它停留即可。反过来，要塞的每次移动必然沿一条这样的边。

因此再从所有陷阱做普通八连通搜索。若方向状态搜索没有答案，而普通搜索可以到达，则这一轰炸选择需要多个机器人。

先用四连通搜索标记全部障碍连通块。分别枚举不轰炸及炸除每一块，重新进行上述两种搜索。所有选择中只要存在一个机器人的方案，就取其最小距离；否则若至少一种选择普通可达，输出 `-2` ，否则输出 `-1` .

## 正确性

追逐规则逐步等价于相邻路径边轴不同，且最后允许牺牲机器人，因此方向状态路径与单机器人方案互相对应，长度保持不变。BFS 给出固定轰炸选择的最短长度。普通连通性与允许补充机器人的可行性互相等价。最后枚举了全部允许的轰炸选择，按题目要求优先选择单机器人方案，所以结果正确。

## 复杂度与实现

令 $V=nm$ ，障碍连通块数为 $c$ .每次搜索的格子状态数为 $O(V)$ ，每个状态最多检查八个邻居，总时间 $O((c+1)V)$ ，额外空间 $O(V)$ .实现逐次复用搜索数组，不为所有轰炸选择同时存储状态。

对角移动只检查目的格。障碍连通块使用四连通；搜索使用八连通，二者不可混淆。没有陷阱时两个搜索的初始队列都为空，所有起点自然输出 `-1` .