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

C++ में दो उंगलियों का उपयोग करके शब्द टाइप करने की न्यूनतम दूरी

मान लीजिए हमारे पास नीचे जैसा कीबोर्ड लेआउट है:

ABCDEF
GHIJKL
MNOPQR
STUVWX
YZ



जहां प्रत्येक अंग्रेजी बड़ा अक्षर कुछ निर्देशांक पर स्थित है, उदाहरण के लिए, अक्षर A (0,0) पर रखा गया है, अक्षर B (0,1) पर, अक्षर P (2,3) पर और अक्षर Z (4,1) पर। अब यदि हमारे पास एक शब्द है, तो हमें केवल दो उंगलियों का उपयोग करके ऐसी स्ट्रिंग को टाइप करने के लिए न्यूनतम कुल दूरी ज्ञात करनी है। दो स्थानों (x1,y1) और (x2,y2) के बीच की दूरी |x1 - x2| + |y1 - y2| है। और हम कीबोर्ड पर किसी भी स्थिति से शुरू कर सकते हैं।

यदि इनपुट "HAPPY" है, तो आउटपुट 6 होगा: H से शुरू करें (लागत 0), फिर A (H से A की लागत 2), फिर P (लागत 0), फिर फिर P (लागत 0), और अंत में Y (P से Y की लागत 4), कुल लागत 2 + 4 = 6।

हल करने के चरण

  • एक मैप memo परिभाषित करें

  • getHash() फ़ंक्शन परिभाषित करें जो स्थिति को हैश करता है

  • getXY() फ़ंक्शन परिभाषित करें जो वर्ण से निर्देशांक प्राप्त करता है

  • getDist() फ़ंक्शन परिभाषित करें जो दो स्थितियों के बीच मैनहट्टन दूरी की गणना करता है

  • solve() फ़ंक्शन परिभाषित करें जो पुनरावर्ती रूप से दोनों उंगलियों की स्थिति और वर्तमान इंडेक्स के लिए न्यूनतम दूरी की गणना करता है

  • मुख्य विधि से: solve(-1, -1, -1, -1, word, 0) लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    map<int, int> memo; 
    int getHash(int a, int b, int c, int d, int e) { 
        int temp = 0; 
        while (a) { temp = temp * 10 + a % 10; a /= 10; } 
        while (b) { temp = temp * 10 + b % 10; b /= 10; } 
        while (c) { temp = temp * 10 + c % 10; c /= 10; } 
        while (d) { temp = temp * 10 + d % 10; d /= 10; } 
        while (e) { temp = temp * 10 + e % 10; e /= 10; } 
        return temp; 
    } 
    pair<int, int> getXY(char c) { 
        pair<int, int> ret; 
        int a = c - 'A'; 
        ret.second = a % 6; 
        ret.first = a / 6; 
        return ret; 
    } 
    int getDist(int a, int b, int c, int d) { 
        if (a == -1 && b == -1) return 0; 
        return abs(b - d) + abs(a - c); 
    } 
    int solve(int x1, int y1, int x2, int y2, string word, int idx) { 
        if (idx == word.size()) return 0; 
        int state = getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2); 
        if (memo.find(state) != memo.end()) return memo[state]; 
        pair<int, int> temp = getXY(word[idx]); 
        int A = getDist(x1, y1, temp.first, temp.second) + solve(temp.first, temp.second, x2, y2, word, idx + 1); 
        int B = getDist(x2, y2, temp.first, temp.second) + solve(x1, y1, temp.first, temp.second, word, idx + 1); 
        int ans = min(A, B); 
        return memo[state] = ans; 
    } 
    int minimumDistance(string word) { 
        memo.clear(); 
        return solve(-1, -1, -1, -1, word, 0); 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.minimumDistance("HELLO")); 
    return 0; 
}

इनपुट

"HELLO"

आउटपुट

4
  1. - C++ में दो आयतों के ओवरलैप होने की जांच करना

    हम जानते हैं कि एक आयत को दो निर्देशांकों का उपयोग करके दर्शाया जा सकता है: ऊपरी बायां कोना (top-left corner) और निचला दायां कोना (bottom-right corner)। मान लीजिए दो आयत हैं, हमें जांचना है कि ये दोनों ओवरलैप होते हैं या नहीं। चार निर्देशांक बिंदु (l1, r1) और (l2, r2) हैं। l1 पहले आयत का ऊपरी-ब

  1. - C++ में ++ ऑपरेटर का उपयोग करके दो संख्याओं को जोड़ना

    प्रोग्रामिंग में, ++ ऑपरेटर एक इंक्रीमेंट ऑपरेटर है जो ऑपरेंड के मान को 1 से बढ़ाता है। हम इस ऑपरेटर का उपयोग करके दो संख्याओं को संख्या a में 1 को b बार जोड़कर जोड़ सकते हैं। उदाहरण: Input: a = 31 , b = 4 Output: 35 व्याख्या - 31 में चार बार 1 जोड़ने पर, योग 31 +1+1+1+1 = 35 होता है। एल्गोरिदम इनपु

  1. - C++ में न्यूनतम तुलना का उपयोग करके तीन में से मध्य मान खोजें

    इस अनुभाग में, हम देखेंगे कि तीन दिए गए मानों की तुलना करके उनमें से मध्य मान कैसे खोजा जाए। तो यदि तीन संख्याएं दी गई हैं जैसे (10, 30, 20), तो यह 20 ढूंढेगा क्योंकि यह मध्य तत्व है। आइए पहले एल्गोरिदम देखें, फिर हम उस एल्गोरिदम को C++ कोड में लागू करेंगे। एल्गोरिदम middle_of_three(a, b, c): Inpu