最少骑士移动

描述

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

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

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

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

编程练习

C++

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

让我们回顾一下解法：

C++

1class hash {
2  public:
3    size_t operator()(std::pair<int,int> a) const {
4        return a.first * 1000 + a.second;
5    }
6};
7
8int dfs(int x, int y, std::unordered_map<std::pair<int, int>, int, hash>&moves) {
9    if (moves.count({x,y})) {
10        return moves[{x,y}];
11    }
12    // 由于对称性，取绝对值
13    int res = std::min(dfs(abs(x-2),abs(y-1), moves), dfs(abs(x-1),abs(y-2), moves)) + 1; 
14    return moves[std::make_pair(x,y)] = res;
15}
16
17int minimumKnightMoves(int x, int y) {
18   
19    std::unordered_map<std::pair<int,int>, int, hash> moves;
20    // 基础情况
21    moves[std::make_pair(0,0)] = 0;
22    moves[std::make_pair(1,1)] = moves[std::make_pair(2,0)] = moves[std::make_pair(0,2)] = 2;
23    moves[std::make_pair(1,0)] = moves[std::make_pair(0,1)] = 3;
24	
25    return dfs(abs(x), abs(y), moves);
26}
27
28int main() {
29    
30    // 你的代码放在这里
31    std::cout << std::to_string(minimumKnightMoves(2, 1)) <<std::endl;
32    std::cout << std::to_string(minimumKnightMoves(2, 0)) <<std::endl;
33    std::cout << std::to_string(minimumKnightMoves(3, 1)) <<std::endl;
34    std::cout << std::to_string(minimumKnightMoves(5, 5)) <<std::endl;
35}

复杂度分析

时间复杂度

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

空间复杂度

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