最少骑士移动

描述

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

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

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

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

编程练习

Java

1class Solution {
2    public static int minimumKnightMoves(int x, int y) {
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. 选择步数最少的路径，并回溯至原始输入坐标。

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

Java

1class Solution {
2    public static HashMap<String, Integer> moves = new HashMap<>();
3    public static int dfs(int x, int y) {
4        String key = x + ", " + y;
5        if (moves.containsKey(key)) {
6            return moves.get(key);
7        }
8        int res = Math.min(dfs(Math.abs(x - 2), Math.abs(y - 1)), 
9                           dfs(Math.abs(x - 1), Math.abs(y - 2))) + 1;
10        moves.put(x + ", " + y, res);
11        return res;
12    }
13
14    public static int minimumKnightMoves(int x, int y) {
15        moves.put("0, 0", 0);
16        moves.put("1, 1", 2);
17        moves.put("2, 0", 2);
18        moves.put("0, 2", 2);
19        moves.put("1, 0", 3);
20        moves.put("0, 1", 3);
21
22        return dfs(x, y);
23    }
24
25    public static void main(String args[]) {
26        System.out.println(minimumKnightMoves(2, 1));
27        System.out.println(minimumKnightMoves(2, 0));
28        System.out.println(minimumKnightMoves(3, 1));
29        System.out.println(minimumKnightMoves(5, 5));
30    }
31}

复杂度分析

时间复杂度

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

空间复杂度

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