两名角色共用狭窄地图时怎样规划不相撞的同步路线:过程核对第26例

  • 2026-11-20
  • 1

两名角色各自走最短路,并不能保证它们在同一时刻不会占到同一个格子。把两人的位置合起来作为一个状态,再按共同的一拍扩展,才能同时考虑让行与等待。

本例规则与输入

本例四乘四方格,每拍每人可以停留或走到一个上下左右空格。禁止两人下一拍占同一格,也禁止同一拍沿同一条边对向交换位置。目标是让两人同时处于各自终点,已经到达终点的人仍允许临时离开。

格号为行乘四加列,零行零列开始。墙[8, 9, 15],起点[4, 13],目标[6, 0]。

逐步计算记录

地图,#为墙,其余是格号: 00 01 02 03 04 05 06 07 # # 10 11 12 13 14 # 拍数 | 角色一格号 | 角色二格号 | 本拍等待角色 0 | 4 | 13 | 开始 1 | 4 | 14 | [1] 2 | 4 | 10 | [1] 3 | 4 | 6 | [1] 4 | 4 | 2 | [1] 5 | 5 | 1 | [] 6 | 6 | 0 | [] 共同完成的最少拍数为6。

表中编号用于区分本例对象,不代表任何真实产品的默认规则。输入、处理顺序与边界约定都属于题目的一部分;请先按相同规则复算,再比较不同实现。分数保留精确值,若自行改用小数,应把显示舍入与实际计算误差分开。

独立核对方法

逐拍路线列出两个人的位置、各自动作和是否等待。搜索按拍数从小到大展开联合状态,首次到达目标联合状态得到最少总拍数。验收不仅检查最终落点,还逐步检查墙、步长、同格和对向交换。

独立复核先枚举所有合法的双人位置组合,再按相邻关系建立联合图,逐层求可达集合。目标不应出现在更早的一层。表中的停留也是一项明确动作,并不表示输入丢失;某些地图中主动等待恰好是避免堵塞所必需的。

适用边界

优化的是两人一起完成所需拍数,不是两人移动步数之和。动作始终同步,不包含半拍交错或连续身体尺寸。角色更多时联合状态会快速增长,本例只用于说明冲突为何不能仅靠两条独立最短路判断。

改变输入后,建议先找到第一处不同的中间结果,再追查它所依赖的条件。不要仅因为最后一个数看起来接近,就认定全过程相同。把原始记录、选择理由与边界情况保留下来,更容易区分机制差异和实现失误。