資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告