数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 次查看
广告