मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [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] := min(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));
}
};
int main(){
Solution ob;
cout << (ob.minKnightMoves(5, 5));
}
इनपुट
5 5
आउटपुट
4