C++ 中的最小骑士移动

假设我们有一个坐标范围从负无穷到正无穷的无限棋盘，并且我们有一个位于方格 [0, 0] 的骑士。骑士可以执行 8 种可能的移动，如下所示。每次移动都是在一个基数方向上移动两个方格，然后在一个正交方向上移动一个方格。

我们必须找到将骑士移动到方格 [x, y] 所需的最小步数。保证答案存在。

因此，如果输入类似于 x = 5 和 y = 5，则输出将为 4。这将类似于 [0,0] → [2,1] → [4,2] → [3,4] → [5,5]

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个映射 m

  • 定义一个名为 solve() 的方法，它将接收 x 和 y

  • 如果 x + y = 0，则返回 0，如果 x + y = 2，则返回 2

  • 使用 (x, y) 创建一个对 temp

  • 如果 m 包含对 temp，则返回 m[temp]

  • 返回 m[temp] := solve(|x - 1|, |y - 2|)，[solve(|x - 2|, |y - 1|) + 1] 的最小值

  • 从主方法中调用 solve(|x|, |y|) 并返回其值

示例（C++）

让我们查看以下实现以更好地理解：

 实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   map < pair <int, int>, int > dp;
   int solve(int x, int y){
      if(x + y == 0) return 0;
      if (x + y == 2) return 2;
      pair <int, int> temp({x, y});
      if(dp.count(temp)) return dp[temp];
      return dp[temp] = min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1))) + 1;
   }
   int minKnightMoves(int x, int y) {
      return solve(abs(x), abs(y));
   }
};
main(){
   Solution ob;
   cout << (ob.minKnightMoves(5, 5));
}

输入

5
5

输出

4

更新于： 2020年4月29日

727 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告