最小骑士移动

描述

我们有一个无限的国际象棋棋盘，坐标范围从负无穷到正无穷。我们的骑士起始于方格 (0, 0)。

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

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

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

编程练习

Kotlin

1internal object Solution {
2    fun minimumKnightMoves(x: Int, y: Int): Int {
3        // 请在此处编写你的代码
4        return -1
5    }
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. 选择步数最少的路径，并回溯至输入坐标。

让我们回顾一下解决方案：

Kotlin

1import java.util.HashMap
2
3internal object Solution {
4    var moves = HashMap<String, Int>()
5    fun dfs(x: Int, y: Int): Int {
6        val key = "$x, $y"
7        if (Solution.moves.containsKey(key)) {
8            return Solution.moves.get(key)!!
9        }
10        val res: Int = Math.min(
11            Solution.dfs(Math.abs(x - 2), Math.abs(y - 1)),
12            Solution.dfs(Math.abs(x - 1), Math.abs(y - 2))
13        ) + 1
14        Solution.moves.put("$x, $y", res)
15        return res
16    }
17
18    fun minimumKnightMoves(x: Int, y: Int): Int {
19        Solution.moves.put("0, 0", 0)
20        Solution.moves.put("1, 1", 2)
21        Solution.moves.put("2, 0", 2)
22        Solution.moves.put("0, 2", 2)
23        Solution.moves.put("1, 0", 3)
24        Solution.moves.put("0, 1", 3)
25        return Solution.dfs(Math.abs(x), Math.abs(y))
26    }
27}
28
29fun main() {
30    println(Solution.minimumKnightMoves(2, 1))
31    println(Solution.minimumKnightMoves(2, 0))
32    println(Solution.minimumKnightMoves(3, 1))
33    println(Solution.minimumKnightMoves(5, 5))
34}

复杂度分析

时间复杂度

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

空间复杂度

我们可能需要存储所有方格的移动次数，因此空间复杂度也是二次的。