C++ এ দুটি আঙুল ব্যবহার করে একটি শব্দ টাইপ করার ন্যূনতম দূরত্ব

ধরুন আমাদের নিচের মত একটি কীবোর্ড লেআউট আছে −

যেখানে প্রতিটি ইংরেজি বড় হাতের অক্ষর কিছু স্থানাঙ্কে অবস্থিত, উদাহরণস্বরূপ, A অক্ষরটি (0,0) এ স্থাপন করা হয়েছে, অক্ষর Bটি (0,1), অক্ষর Pটি (2,3) এ স্থাপন করা হয়েছে। এবং Z অক্ষরটি (4,1) এ স্থাপন করা হয়েছে। এখন যদি আমাদের কাছে একটি শব্দ থাকে তবে আমাদের শুধুমাত্র দুটি আঙ্গুল ব্যবহার করে এই ধরনের স্ট্রিং টাইপ করার জন্য সর্বনিম্ন মোট দূরত্ব খুঁজে বের করতে হবে। দুটি স্থান (x1,y1) এবং (x2,y2) এর মধ্যে দূরত্ব হল |x1 - x2| + |y1 - y2|। এবং আমরা কীবোর্ডের যেকোনো অবস্থান থেকে শুরু করতে পারি।

সুতরাং, যদি ইনপুটটি "হ্যাপি" এর মত হয়, তাহলে আউটপুট হবে 6, যেমন H দিয়ে শুরু করুন, তাই খরচ 0, তারপর A, সুতরাং H থেকে A থেকে 2, তারপর P, সুতরাং খরচ 0, তারপর আবার। P, খরচ হল 0, এবং অবশেষে Y, তাই P থেকে Y পর্যন্ত খরচ হল 4, তাই মোট খরচ হল 6 + 4 =10৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র মেমো সংজ্ঞায়িত করুন

• একটি ফাংশন getHash() সংজ্ঞায়িত করুন, এটি a, b, c, d, e,

  লাগবে

• তাপমাত্রা :=0

• a যখন শূন্য নয়, −

  করুন

  • temp :=temp * 10 + a mod 10, a :=a / 10

• যখন b অ-শূন্য, −

  করুন

  • temp :=temp * 10 + b mod 10, b :=b / 10

• যখন c অ-শূন্য, কর −

  • temp :=temp * 10 + d mod 10, d :=d / 10

• যখন e অ-শূন্য, কর

  • temp :=temp * 10 + e mod 10, e :=e / 10

• রিটার্ন টেম্প

• একটি পদ্ধতি সংজ্ঞায়িত করুন getXY(), এটি c

  লাগবে

  • এক জোড়া ret সংজ্ঞায়িত করুন

  • a :=c - 'A'

    এর ASCII

  • ret.second :=a mod 6

  • ret.first :=a / 6

  • রিটার্ন রিটার্ন

• একটি ফাংশন getDist() সংজ্ঞায়িত করুন, এটি a, b, c, d,

  লাগবে

• a যদি -1 এর মত হয় এবং b -1 এর মত হয়, তাহলে −

  • রিটার্ন 0

• ফেরত |(b - d) + |a - c||

• একটি ফাংশন সমাধান সংজ্ঞায়িত করুন, এটি 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))

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

• উত্তর :=সর্বনিম্ন A এবং B

• রিটার্ন মেমো[state] =ans

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• রিটার্ন সমাধান(-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