最小骑士移动

描述

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

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

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

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

自行实现

1fn minimumKnightMoves(x: i32, y: i32) -> i32 {
2    // 请在此处编写你的代码。
3    return -1;
4}

解法

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

让我们回顾一下解法：

1use std::collections::HashMap;
2use std::cmp;
3
4fn dfs(x: i32, y: i32, moves: &mut HashMap<(i32, i32), i32>) -> i32 {
5    if !moves.contains_key(&(x, y)) {
6        let result = cmp::min(dfs((x - 1).abs(), (y - 2).abs(), moves), 
7                              dfs((x - 2).abs(), (y - 1).abs(), moves)) + 1;
8        moves.entry((x, y)).or_insert(result);
9    }
10    *moves.get(&(x, y)).unwrap()
11}
12
13fn minimum_knight_moves(x: i32, y: i32) -> i32 {
14    let mut moves = HashMap::new();
15
16    // 基础情况
17    moves.insert((0, 0), 0);
18    moves.insert((1, 1), 2);
19    moves.insert((2, 0), 2);
20    moves.insert((0, 2), 2);
21    moves.insert((1, 0), 3);
22    moves.insert((0, 1), 3);
23
24    let (x1, y1) = if x > y { (y, x) } else { (x, y) };
25
26    dfs(x1.abs(), y1.abs(), &mut moves)
27}
28
29fn main() {
30    println!("{}", minimum_knight_moves(2, 1));
31    println!("{}", minimum_knight_moves(2, 0));
32    println!("{}", minimum_knight_moves(3, 1));
33    println!("{}", minimum_knight_moves(5, 5));
34}

复杂度分析

时间复杂度

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

空间复杂度

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