最小骑士移动

描述

我们有一个从负无穷到正无穷的无限棋盘，骑士从坐标 (0, 0) 开始。

骑士在任意时刻有八种可能的移动方式。它以“L”形移动，即可以先垂直方向移动两格，再水平方向移动一格；或者先水平方向移动两格，再垂直方向移动一格。

你需要找出骑士从原点 (0, 0) 移动到目标坐标 (x, y) 所需的最少步数。我们假设给定的坐标始终可达，并且满足约束条件 |x| + |y| ≤ 300。

例如，当输入坐标为 (5, 5) 时，你需要找出骑士从原点到达该坐标的最少步数。在这种情况下，程序应输出 4，因为骑士需要 4 步才能到达目标位置。

编程练习

Swift

1import Swift
2
3func minimumKnightMoves(x: Int, y: Int) -> Int {
4    // 请在此处编写你的代码。
5    return -1
6}

解法

注意，骑士向正负坐标轴方向移动具有对称性，到达正负坐标所需的步数相同。骑士在任意时刻都可以向八个方向移动，通过将以下偏移量添加到当前位置来实现：[{1, 2}, {2, 1}, {-1, 2}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {2, -1}]。

因此，我们可以避免处理负坐标，将问题简化为仅在第一象限中求解，始终保持坐标为正值。原点固定不变，可以通过取坐标的绝对值来转换输入坐标。这样我们就能确定移动方向。此时，我们只需考虑两个方向的移动，即加上以下偏移量：[{-1, -2}, {-2, -1}]，并只探索坐标的绝对值。

以下是该解法的实现步骤：

1. 取坐标的绝对值 (x, y)。
2. 手动初始化一个映射表，记录到达原点所需最少步数。映射表以坐标为键，最少步数为值。
3. 从输入坐标出发，以深度优先的方式回溯至原点。
4. 如果某个坐标已被访问过，则直接返回其对应的步数；否则，继续探索骑士可移动到的下一个坐标。
5. 选择步数最少的路径，并回溯至原始输入坐标。

让我们回顾一下解法：

Swift

1import Swift
2
3struct Tuple: Hashable {
4    var first: Int = 0
5    var second: Int = 0
6
7    init(_ first: Int, _ second: Int) {
8        self.first = first
9        self.second = second
10    }
11
12    func hash(into hasher: inout Hasher) {
13        hasher.combine(first)
14        hasher.combine(second)
15    }
16}
17
18func dfs(x: Int, y: Int, moves: inout [Tuple: Int]) -> Int {
19    let arr: [Tuple] = (moves.keys.filter { $0.first == x && $0.second == y })
20    if arr.count > 0 {
21        let tuple: Tuple = Tuple(x, y)
22        return moves[tuple]!
23    }
24    // 因为对称性，取绝对值
25    let op1 = dfs(x: abs(x - 2), y: abs(y - 1), moves: &moves)
26    let op2 = dfs(x: abs(x - 1), y: abs(y - 2), moves: &moves)
27    let res: Int = (op1 <= op2 ? op1 : op2) + 1
28    let tuple: Tuple = Tuple(x, y)
29    moves[tuple] = res
30    return res
31}
32
33func minimumKnightMoves(x: Int, y: Int) -> Int {
34    var moves: [Tuple: Int] = [:]
35    // 基础情况
36    moves[Tuple(0, 0)] = 0
37    moves[Tuple(1, 1)] = 2
38    moves[Tuple(2, 0)] = 2
39    moves[Tuple(0, 2)] = 2
40    moves[Tuple(1, 0)] = 3
41    moves[Tuple(0, 1)] = 3
42
43    return dfs(x: abs(x), y: abs(y), moves: &moves)
44}
45
46// 你的代码放在这里
47print(String(minimumKnightMoves(x: 2, y: 1)))
48print(String(minimumKnightMoves(x: 2, y: 0)))
49print(String(minimumKnightMoves(x: 3, y: 1)))
50print(String(minimumKnightMoves(x: 5, y: 5)))

复杂度分析

时间复杂度

我们处理的是从原点到目标坐标 [x, y] 的一个子矩阵。原点固定，可能需要遍历所有格子。因此时间复杂度为 $O(|x| \times |y|)$。

空间复杂度

可能需要存储所有格子的最少步数，因此空间复杂度也是二次的。