Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

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

हमें नाइट को [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

  1. C++ में बाइनरी ट्री की न्यूनतम गहराई C++ में बाइनरी ट्री की न्यूनतम गहराई

    समस्या विवरण मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस ट्री की न्यूनतम गहराई ज्ञात करनी है। जैसा कि हम जानते हैं, न्यूनतम गहराई रूट नोड से निकटतम लीफ नोड तक के सबसे छोटे पथ पर नोड्स की संख्या है। उदाहरण यदि इनपुट ट्री है: तो आउटपुट होगा 2 हल करने का दृष्टिकोण इस समस्या को हल करने के लिए निम

  1. C++ में शतरंज बोर्ड पर घोड़े की संभावना C++ में शतरंज बोर्ड पर घोड़े की संभावना

    मान लीजिए हमारे पास एक NxN शतरंज बोर्ड है, एक घोड़ा r-वें पंक्ति और c-वें स्तंभ से शुरू होता है और ठीक K चालें चलने का प्रयास करता है। यहां पंक्तियों और स्तंभों को 0 से अनुक्रमित किया जाता है, इसलिए शीर्ष-बायां वर्ग (0, 0) है, और निचला-दायां वर्ग (N-1, N-1) है। एक घोड़ा एक सेल से 8 अलग-अलग सेलों म

  1. - C++ में सभी तत्वों को समान बनाने के लिए न्यूनतम मूव्स

    समस्या कथन N तत्वों की एक सरणी और एक पूर्णांक K दिया गया है। दी गई सरणी पर निम्न ऑपरेशन किसी भी संख्या में बार करना अनुमत है: K-वें तत्व को सरणी के अंत में डालें और सरणी के पहले तत्व को हटाएं। कार्य सरणी के सभी तत्वों को समान बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढना है। यदि संभव नहीं