思路

• 状态设计：由于两角色始终同坐标，状态为 $(r,c,h_1,h_2)$，其中 $h_1,h_2$ 分别为当前两人的血量（均在 $1\ldots 20$）。

• 转移规则：

  • 尝试四方向，共 $4$ 个方向。
  • 若两图下一格皆为障碍，则跳过。
  • 若仅一侧为障碍，则对应方需要 $h>1$ 才能前进，并使该方血量减 $1$。
  • 若两侧为空地，则血量不变。

• 搜索策略：对状态做按层的 BFS。边权均为 $1$，因此首次到达终点的一层即为最短步数所在层。

题目内容

在量子纠缠的平行宇宙中，探险家「艾克斯」和「泽塔」需要同步操控两个镜像角色，穿越地形迥异的双子地图。他们的命运通过量子纽带相连——移动必须完全同步，障碍物会消耗血量，唯有协作才能抵达终点。

双地图寻路，两个镜像地图尺寸相同，均为 $N×M$ ($N$行$M$列)，角色固定左上起点 $(0,0)$ ，右下终点 $(N-1,M-1)$ ，起点和终点均为空地。地图中障碍物用 # 表示，空地用 . 表示，两个地图的障碍分布不同。两个地图上的角色必须同步移动：在任一时刻，两者所处的位置相同，所移动的步数相同，且下一步的移动方向一致。移动方向只能是上下、左、右四个方向，不允许斜向移动。

• 如果选择某个方向后，两张地图中对应的下一格均为空地，则两名角色均能正常移动至该格，步数增加 step+1 。

• 如果选择某个方向后，两张地图中对应的下一格均为障碍，则不能沿该方向移动，需另选方向。