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

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

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

इसलिए, यदि इनपुट "हैप्पी" की तरह है, तो आउटपुट 6 होगा, जैसा कि एच से शुरू होता है, इसलिए लागत 0 है, फिर ए, इसलिए एच से ए तक की लागत 2 है, फिर पी, इसलिए लागत 0 है, फिर से P, लागत 0 है, और अंत में Y, इसलिए P से Y तक की लागत 4 है, इसलिए कुल लागत 6 + 4 =10 है।

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

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

• फ़ंक्शन getHash() को परिभाषित करें, इसमें a, b, c, d, e,

  . लगेगा

• अस्थायी:=0

• जबकि a गैर-शून्य है, करें -

  • अस्थायी:=अस्थायी * 10 + एक मॉड 10, ए:=ए / 10

• जबकि b गैर-शून्य है, करें −

  • अस्थायी:=अस्थायी * 10 + बी मॉड 10, बी:=बी / 10

• जबकि c गैर-शून्य है, करें −

  • अस्थायी:=अस्थायी * 10 + डी मॉड 10, डी:=डी / 10

• जबकि ई गैर-शून्य है, करें

  • अस्थायी:=अस्थायी * 10 + ई मॉड 10, ई:=ई / 10

• वापसी अस्थायी

• एक विधि को परिभाषित करें getXY(), इसमें c

  लगेगा

  • एक जोड़ी रिट परिभाषित करें

  • a :=c - 'A' का ASCII

  • ret.second :=एक मॉड 6

  • ret.first :=a / 6

  • वापसी रिट

• फ़ंक्शन getDist() को परिभाषित करें, इसमें a, b, c, d,

  . लगेगा

• यदि a, -1 के समान है और b, -1 के समान है, तो -

  • वापसी 0

• वापसी |(बी - डी) + |ए - सी||

• एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें x1, y1, x2, y2, शब्द, idx,

  लगेगा।

• यदि idx शब्द के आकार के समान है, तो -

  • वापसी 0

• राज्य:=getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2)

• अगर राज्य मेमो में है तो -

  • वापसी ज्ञापन [राज्य]

• एक जोड़ी अस्थायी परिभाषित करें:=getXY(word[idx])

• उत्तर:=0

• A:=getDist(x1, y1, temp.first, temp.second +solve(temp.first, temp.second, x2, y2, word, idx + 1))

• बी:=getDist(x2, y2, temp.first, temp.second +solve(x1, y1, temp.first, temp.second, word, idx + 1))

• उत्तर:=न्यूनतम ए और बी

• वापसी ज्ञापन [राज्य] =उत्तर

• मुख्य विधि से निम्न कार्य करें -

• वापसी हल (-1, -1, -1, -1, शब्द, 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 ans = 0;
      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);
      ans = min(A, B);
      return memo[state] = ans;
   }
   int minimumDistance(string word){
      memo.clear();
      return solve(-1, -1, -1, -1, word, 0);
   }
};
main(){
   Solution ob;;
   cout << (ob.minimumDistance("HELLO"));
}

इनपुट

"HELLO"

आउटपुट

4