最小骑士移动

描述

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

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

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

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

编程练习

C#

1using System;
2using System.Collections.Generic;
3
4class Solution {
5    public static int minimumKnightMoves(int x, int y) {
6        // 请在此处编写你的代码
7        return -1;
8    }
9}

解法

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

让我们回顾一下解法：

C#

1using System;
2using System.Collections.Generic;
3
4class Solution {
5    public static Dictionary<string, int> moves = new Dictionary<string, int>();
6    public static int dfs(int x, int y){
7        string key = x + ", " + y; 
8        if(moves.ContainsKey(key)){
9            return moves[key];
10        }
11        int res = Math.Min(dfs(Math.Abs(x-2), Math.Abs(y-1)), dfs(Math.Abs(x-1), Math.Abs(y-2))) + 1; 
12        moves[x + ", " + y] = res;
13        return res;
14    }
15
16    public static int minimumKnightMoves(int x, int y){
17        
18        moves["0, 0"] = 0;
19        moves["1, 1"] = 2;
20        moves["2, 0"] = 2;
21        moves["0, 2"] = 2;
22        moves["1, 0"] = 3;
23        moves["0, 1"] = 3;
24        
25        return dfs(x, y);
26    }
27
28    public static void Main() {
29        Console.WriteLine(minimumKnightMoves(2, 1));
30        Console.WriteLine(minimumKnightMoves(2, 0));
31        Console.WriteLine(minimumKnightMoves(3, 1));
32        Console.WriteLine(minimumKnightMoves(5, 5));
33    }
34}

复杂度分析

时间复杂度

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

空间复杂度

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