骑士的最少移动次数
Minimum Knight Moves
题目详情
问题：骑士的最少移动次数
考察：图
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/minimum-knight-moves/
In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps to move the knight to the square [x, y]. It is guaranteed the answer exists.
Example 1:
Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] -> [2, 1]
Example 2:
Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5]
Constraints:
-300 <= x, y <= 300- The answer is guaranteed to exist.
解析
思路：棋盘关于坐标轴和对角线对称，可把目标转到第一象限。用 BFS 从 (0,0) 搜索，限制到目标附近的合理边界；也可用数学递推处理大坐标。
复杂度：BFS 状态数与目标距离平方相关；常见约束下可接受，空间同状态数。