C++ में न्यूनतम नाइट मूव्स

मान लीजिए कि हमारे पास एक अनंत शतरंज की बिसात है जिसमें -infinity से +infinity तक के निर्देशांक हैं, और हमारे पास वर्ग [0, 0] पर एक नाइट है। एक शूरवीर के पास 8 संभावित चालें हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक चाल एक कार्डिनल दिशा में दो वर्ग है, फिर एक वर्ग एक ओर्थोगोनल दिशा में है।

हमें नाइट को वर्ग [x, y] में ले जाने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी। यह गारंटी है कि उत्तर मौजूद है।

तो अगर इनपुट x =5 और y =5 जैसा है, तो आउटपुट 4 होगा। यह [0,0] → [2,1] → [4,2] → [3,4] → [ जैसा होगा। 5,5]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

नक्शा परिभाषित करें मी
हल () नामक एक विधि को परिभाषित करें, इसमें x और y लगेंगे
यदि x + y =0 है, तो 0 लौटाएँ, यदि x + y =2 है, तो 2 लौटाएँ
(x, y)
. का उपयोग करके एक जोड़ी अस्थायी बनाएं
यदि m में युग्म अस्थायी है, तो m[temp]
वापसी m[temp] :=मिनट का हल (|x - 1|, |y - 2|)), [हल करें(|x - 2|, |y - 1|)) + 1]
मुख्य विधि से, हल (|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