标签: 广度优先搜索
难度: Medium
Submission
运行时间: 35 ms
内存: 0.0 MB
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
x = abs(x)
y = abs(y)
res = 0
while x > 4 or y > 4:
res += 1
if x >= y:
x -= 2
y -= 1 if y >= 1 else -1
else:
y -= 2
x -= 1 if x >= 1 else -1
moves = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))
q = deque([(0, 0, 0)])
while q:
i, j, s = q.popleft()
if i == x and j == y:
return res + s
for di, dj in moves:
if (x - i) * di > 0 or (y - j) * dj > 0:
q.append((i + di, j + dj, s + 1))
Explain
该题解使用了贪心算法和广度优先搜索（BFS）的组合来找到从原点(0,0)到目标位置(x,y)的最少骑士移动次数。首先，由于骑士的移动是对称的，我们只考虑x和y的绝对值。在较大的坐标区域（x或y大于4），使用贪心算法快速减少距离，每次尽可能地向目标位置靠近。当x和y都小于等于4时，转而使用BFS考虑所有可能的骑士移动，直到找到到达目标坐标(x, y)的最短路径。该方法先快速减少距离，后细致搜索，平衡了效率和准确性。
时间复杂度: O(max(x, y))
空间复杂度: O(1)
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
x = abs(x)
y = abs(y)
res = 0
# 使用贪心算法减少大坐标值
while x > 4 or y > 4:
res += 1
if x >= y:
x -= 2
y -= 1 if y >= 1 else -1
else:
y -= 2
x -= 1 if x >= 1 else -1
# 定义骑士的可能移动方向
moves = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))
q = deque([(0, 0, 0)])
# 使用BFS搜索最短路径
while q:
i, j, s = q.popleft()
if i == x and j == y:
return res + s
for di, dj in moves:
if (x - i) * di > 0 or (y - j) * dj > 0:
q.append((i + di, j + dj, s + 1))
Explore
在x或y大于4时使用贪心算法可以快速减少到目标的距离，从而减少计算量和提高效率。贪心算法在大尺度上能够有效地接近目标，因此适合在较大的坐标区域使用。相较之下，BFS虽然可以找到最优解，但在大规模搜索时非常耗时和内存消耗大，因为需要探索大量的状态。因此，结合使用贪心算法和BFS，可以在保证找到最短路径的同时，尽可能提高算法的效率。
选择`x -= 2`和`y -= 1`是基于骑士在棋盘上的移动方式（L形）。此种移动方式能够在保持x和y都减小的同时，使用最少的步数接近目标位置。虽然这样的移动在局部看来不一定是最优的，但在全局上，这种策略能够快速减少x和y的值，尤其是当x和y相差较大时。在实际应用中，此策略经常能有效减少计算步骤，尽管它不保证每一步都是局部最优解。
在BFS搜索中，条件`(x - i) * di > 0 or (y - j) * dj > 0`用于确定移动的方向是否使得当前位置接近目标位置。此条件确保了在x或y方向上的移动是朝向目标的，避免了向远离目标的方向移动。这种方式可以减少无效的探索和提高搜索的效率，确保每一步都在尽可能地接近目标。
题解中未提及处理重复状态或已访问过的坐标点的机制，这可能会导致算法效率降低，因为可能会重复探索同一坐标点。在实际应用中，通常会使用一个集合或数组来记录已访问过的位置，防止重复访问，从而提高效率。未使用此机制可能会导致BFS搜索的时间和空间复杂度增加。