无限棋盘骑士最短路径BFS算法时间复杂度O(m*n)的疑问

首先明确核心结论：虽然棋盘是无限的，但BFS实际只会探索围绕起点和目标的有限区域，且每个位置仅被访问一次，因此时间复杂度是O(mn)而非指数级。下面分几点拆解解释：

1. 为什么不会是O(8^s)？ #

你提到的O(8^s)是假设每个位置的8种移动都会被重复探索，但代码里的visited集合彻底避免了这种情况：每个坐标(x,y)只会被加入队列一次、处理一次。也就是说，即使骑士有8种移动方式，也不会对同一个位置进行多次处理，自然不会出现指数级的路径膨胀。

2. 为什么是O(mn)？ #

这里的m是起点与目标的水平距离（|x₁-x₂|），n是垂直距离（|y₁-y₂|），原因在于：

• 骑士的移动特性决定了，要到达目标位置，不需要探索距离起点或目标过远的区域。BFS是按「步数层」遍历的，当我们找到目标位置时，所有可能的更短路径已经被处理完毕，那些远离目标的位置根本不会被纳入探索范围——因为它们无法带来更短的路径，而且一旦某个位置被访问过，后续就不会再处理它。
• 实际被访问的所有位置，都落在以起点和目标为对角线的矩形及其周边的小范围内，这个区域的面积是O(mn)量级的。比如假设起点在(0,0)，目标在(m,n)，我们只会探索x在[-k, m+k]、y在[-k, n+k]的区域（k是和骑士移动步长相关的小常数），总面积约为(m+2k)*(n+2k)，忽略常数项后就是O(mn)。

3. 结合图论复杂度O(V+E)的解释 #

图论中BFS的时间复杂度是O(V+E)，其中V是访问的节点数，E是边数：

• V就是我们实际访问的位置数，也就是上面提到的O(mn)；
• 每个节点最多对应8条边（骑士的8种移动），所以E=O(V)=O(mn)；
• 因此总复杂度O(V+E)=O(mn)+O(mn)=O(mn)。

补充：代码细节验证 #

你的代码里，每次处理一个位置时，只会把未访问过的相邻位置加入队列，且加入后立即标记为已访问。这意味着：

• 队列中不会出现重复位置；
• 队列大小始终控制在已访问区域的范围内，不会无限增长；
• 一旦找到目标位置就立即返回，不会继续探索无关区域。

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