最小骑士移动

描述

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

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

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

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

编程练习

Go

1package main
2import (
3  "fmt"
4  "strconv"
5  "encoding/json"
6)
7
8func minimumKnightMoves(x, y int) int{
9    // 请在此处编写你的代码。
10    return -1
11}

解法

注意，骑士向正负坐标轴方向移动具有对称性。到达正坐标和负坐标所需的步数相同。骑士在任意时刻都可以向八个方向移动，通过将以下偏移量添加到当前位置来实现：[{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. 选择步数最少的路径，并回溯至原始输入坐标。

让我们回顾一下解法：

Go

1package main
2import (
3    "fmt"
4    "math"
5)
6
7type Pair struct {
8    first, second int
9}
10
11func dfs(x int, y int, moves map[Pair]int) int {
12    temp := Pair{x, y}
13    if i, ok := moves[temp]; ok {
14        return i
15    }
16    // 因为对称性，取绝对值
17    pos1 := dfs(int(math.Abs(float64(x-2))), int(math.Abs(float64(y-1))), moves)
18    pos2 := dfs(int(math.Abs(float64(x-1))), int(math.Abs(float64(y-2))), moves)
19
20    res := int(math.Min(float64(pos1), float64(pos2))) + 1
21    moves[temp] = res
22    return res
23}
24
25func minimumKnightMoves(x, y int) int {
26    moves := make(map[Pair]int)
27    // 基础情况
28    moves[Pair{0, 0}] = 0
29    moves[Pair{1, 1}], moves[Pair{2, 0}], moves[Pair{0, 2}] = 2, 2, 2
30    moves[Pair{1, 0}], moves[Pair{0, 1}] = 3, 3
31
32    return dfs(int(math.Abs(float64(x))), int(math.Abs(float64(y))), moves)
33}
34
35func main() {
36    // 测试代码
37    fmt.Println(minimumKnightMoves(2, 1))
38    fmt.Println(minimumKnightMoves(2, 0))
39    fmt.Println(minimumKnightMoves(3, 1))
40    fmt.Println(minimumKnightMoves(5, 5))
41}

复杂度分析

时间复杂度

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

空间复杂度

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