---

1197. 进击的骑士

• 标签：广度优先搜索
• 难度：中等

题目链接

• 1197. 进击的骑士 - 力扣

题目大意

描述：在一个无限大的棋盘上，你的骑士位于坐标 $[0, 0]$ 处。骑士的走法和中国象棋中的"马"一样，走"日"字：即先向左（或右）走 $1$ 格，再向上（或下）走 $2$ 格；或者先向左（或右）走 $2$ 格，再向上（或下）走 $1$ 格。总共有 $8$ 个可能的移动方向。

要求：返回骑士走到目标坐标 $[x, y]$ 所需的最小移动次数。题目保证答案一定存在。

说明：

• $-300 \le x, y \le 300$。
• $0 \le |x| + |y| \le 300$。

示例：

• 示例 1：

输入：x = 2, y = 1
输出：1
解释：[0, 0] → [2, 1]

• 示例 2：

输入：x = 5, y = 5
输出：4
解释：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

解题思路

思路 1：广度优先搜索 + 对称性优化

两个关键优化：

1. 利用对称性：棋盘是对称的。从 $[0,0]$ 到 $[x,y]$ 的最短步数，和到 $[|x|, |y|]$ 是一样的。所以我们可以把目标坐标都取绝对值，只考虑第一象限，减少搜索范围。

2. 限制搜索边界：虽然棋盘无限大，但骑士没必要跑太远再绕回来。把搜索范围限制在 $[-2, x+2]$ 和 $[-2, y+2]$ 之间就够了。允许稍微走到负数区域，是因为有些最短路径需要先往反方向走一步。

拆解步骤：

1. 坐标归一：把目标坐标 $(x, y)$ 取绝对值，转换到第一象限。

2. 准备 BFS：

   • 用一个队列存储待探索的位置，初始放入起点 $(0, 0)$ 和步数 $0$
   • 用一个集合记录已经访问过的位置，防止重复探索

3. 开始一层层探索：

   • 从队列中取出一个位置
   • 如果这个位置就是目标，返回当前步数
   • 否则，尝试 $8$ 个方向的移动
   • 如果新位置在搜索范围内且没访问过，标记为已访问并加入队列，步数加 $1$

4. 重复直到找到目标——因为题目保证答案存在，所以一定能找到。

思路 1：代码

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # 利用对称性，把目标坐标转换到第一象限
        x, y = abs(x), abs(y)

        # 骑士的 8 个可能移动方向
        directions = [
            (2, 1), (1, 2), (-1, 2), (-2, 1),
            (-2, -1), (-1, -2), (1, -2), (2, -1)
        ]

        # BFS：队列里存 (x, y, steps)
        queue = deque([(0, 0, 0)])
        visited = {(0, 0)}

        while queue:
            cur_x, cur_y, steps = queue.popleft()

            # 到达目标位置，返回当前步数
            if cur_x == x and cur_y == y:
                return steps

            # 尝试 8 个方向的移动
            for dx, dy in directions:
                nx, ny = cur_x + dx, cur_y + dy

                # 限制搜索范围，避免跑太远
                # 允许稍微走到负数区域，因为有时需要先退再进
                if (nx, ny) not in visited and -2 <= nx <= x + 2 and -2 <= ny <= y + 2:
                    visited.add((nx, ny))
                    queue.append((nx, ny, steps + 1))

        return -1  # 理论上不会执行到这里

思路 1：复杂度分析

• 时间复杂度：$O((x + y)^2)$。用人话说就是：搜索的区域大致是一个以目标为中心的矩形，面积和 $(x+y)$ 的平方成正比。
• 空间复杂度：$O((x + y)^2)$。visited 集合和队列需要存储搜索过的位置，数量和探索的区域大小相当。