恐怖机器人：题解¶

解法比较¶

出题人解法先按四连通标记障碍组，再在状态 \((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 .