网易通用技术笔试：双人相遇最短回合数

《面试题目》

1. 双人相遇最短回合数：给定一个 n × m 的地图，每个格子要么是空地 .，要么是障碍 #。地图上给定两个人的初始坐标，以及一个终点坐标（坐标均从 1 开始计数）。游戏按回合进行，规则如下：
   • 相遇前：每个回合，两个人各自独立移动一步，可以向上下左右四个方向移动，也可以选择原地不动（即每回合最多移动一格）。
   • 相遇：当且仅当两人停在同一个格子时，视为相遇。仅交换位置不算相遇。
   • 相遇后：每个回合，两人各自可以移动最多两步，同样可以上下左右移动或原地不动。最优策略下两人不会分开。
   • 障碍：. 表示可通行的空地，# 表示障碍，任何人都不能进入障碍格子。
   • 结束条件：当两个人同时位于终点坐标时，游戏结束。
   • 求最少需要多少个回合，才能让两人同时到达终点；如果无法完成，输出 -1。
2. AI Coding 题：强制使用 Python 和 JavaScript，没有提交判分环节，只给基础测试用例，测试用例还得自己写，整体流程很短。

《参考解析》

先看状态怎么定义

最稳的建模是把两个人的坐标和「是否已相遇」一起放进状态：(r1, c1, r2, c2, met)，用 BFS 按回合推进。转移分两种：met = false 时每人最多走一格（含原地不动），组合数最多 9 × 9 = 81 种；met = true 时每人最多走两格，最多 25 × 25 = 625 种。每轮生成新状态后判断两人是否落在同一格，是则把 met 置真。答案就是第一次出现「两人都在终点」时的层数，搜索耗尽还没出现就输出 -1。

两个容易写错的地方：一是「仅交换位置不算相遇」，所以转移里不能把「两人互换了格子」当成相遇事件，必须检查落点是否相同；二是入队时就打访问标记，否则同一个四元组会被反复入队。

状态数才是这道题的坑

四维状态的数量级是 O(n²m²)，n、m 稍微大一点（比如 50 × 50）就是 600 多万个状态乘上几百种转移，必然超时或爆内存。好在题目给了两条能大幅剪枝的性质：相遇前两人各自移动，互不影响；相遇后又总是待在一起。

于是可以拆成三段算，全程只需要三次网格 BFS。设 d1(v)、d2(v) 分别是两人从各自起点到格子 v 的最短步数（四方向、每步一格、含 BFS 常规处理），dT(v) 是 v 到终点的最短步数。因为规则允许原地不动，所以在格子 v 相遇所需的最少回合就是 max(d1(v), d2(v))——先到的一方在 v 上等着即可。相遇之后每人每回合能走两格，两人又同步，所以从 v 到终点还需要 ceil(dT(v) / 2) 个回合。

两者相加，答案就是 min over v [ max(d1(v), d2(v)) + ceil(dT(v) / 2) ]，枚举所有两人都能到达、且能到达终点的格子取最小值。三人同时到达终点的情况也包含在内：取 v 为终点时第二项为 0，结果就是 max(d1(T), d2(T))。如果不存在这样的 v，输出 -1。

为什么这样拆是对的

本质原因是「相遇」把问题切成两个阶段，而切换点只是一个格子。相遇前两人唯一的耦合是必须停在同一格，用「等着」吸收掉到达时间的差；相遇后两人处于同一格、面对同一张图，代价只取决于到终点的距离。这样把 O(n²m²) 的状态空间压成 O(nm)，只有当规则再增加维度（比如两人会互相阻挡、每人有独立体力）时才必须退回四维 BFS。写题时如果来不及推这个结论，就先交四维 BFS 拿小数据的分，但要注意多组测试用例和 -1 的输出格式。

AI Coding 部分怎么应对

这场 AI Coding 的强制语言是 Python 和 JavaScript，没有提交判分，只给基础用例，测试要自己写。没有真实用例就意味着「能跑」不等于「能过」，策略是把精力放在自己构造的用例上：正常路径、单元素、空输入、极值规模各写一组，用断言把预期结果固定下来；再检查输出格式（换行、空格、多组用例的分隔）是否和题面一致。原帖作者的体感是流程太短、写完很早，说明这部分真正区分人的不是速度，而是自测用例的覆盖度。