求解M×N棋盘上两骑士相遇所需的最少移动步数

思路正确性判断 #

你采用的双向BFS思路本质是正确的：分别从黑白骑士的位置出发逐层扩展各自的可达范围，每完成一次移动就检查双方可达范围的交集，存在交集即代表两者可相遇，累计的步数就是最短总步数。双向BFS相比单向BFS能大幅降低搜索时间和空间占用，是这类双起点最短相遇路径问题的最优解法之一。

初始位置相同的场景你的代码可以直接输出0，白走一步相遇、黑白各走一步相遇的场景计数逻辑也符合规则。

现有代码存在的问题 #

1. 不可达判断逻辑错误
   你当前用wp.count == 1 || bp.count == 1作为不可达的判定条件完全不符合实际场景：只有当骑士处于完全无法移动的场景（比如2×2棋盘）时集合大小才会一直为1，绝大多数场景骑士可达位置会逐步增多，该条件会误判。正确的不可达判定应该是：当某次扩展完成后，集合的大小没有发生任何变化，说明已经遍历完该骑士所有可达的位置，此时如果还没有交集，才判定为永远无法相遇。
   另外可以增加前置剪枝：骑士每走一步坐标x+y的和奇偶性会翻转，结合白骑士先手的规则可直接过滤不可能的情况：初始白骑士坐标和为w_sum，黑骑士为b_sum，若两者奇偶性相同，总步数必须为偶数；若不同总步数必须为奇数，不满足该条件可直接返回-1。
2. 扩展逻辑冗余
   你当前的oneMove函数每次遍历所有历史可达位置，会重复计算已经处理过的坐标，导致大量无效运算。
3. 数据结构效率低
   你用Set<[Int]>存储坐标，Swift中数组作为集合元素的哈希计算、等值比较的效率都很低，会拖慢集合交集判断、插入等操作的速度。

性能优化空间 #

• 只遍历新增节点：每次扩展时，只传入上一轮新增的节点集合，而非所有历史可达节点，同时维护全局可达集合用来判重，避免重复处理相同坐标。
• 坐标编码优化：将(x,y)坐标编码为单个整数存储，比如x * (n + 1) + y，改用Set<Int>存储坐标，大幅降低集合操作的开销。
• 小集合优先扩展：每次扩展时优先选择当前节点数更少的集合进行扩展，进一步压缩搜索空间，这是双向BFS的标准优化手段。
• 提前剪枝：输入坐标后先校验相遇必要条件，不符合直接返回-1，无需执行后续BFS流程。

内容的提问来源于stack exchange，提问作者georgevil73