C++-এ দুটি আঙ্গুল দিয়ে ওয়ার্ড টাইপ করার ন্যূনতম দূরত্ব

ধরি একটি কীবোর্ড লেআউট আছে যেন –

প্রতিটি ইংরেজি বড় হাতের অক্ষর একটি কোঅর্ডিনেটে অবস্থিত। যেমন 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; মোট 6)।

সমাধানের ধাপসমূহ

• memo নামক একটি ম্যাপ সংজ্ঞায়িত করুন

• getHash() ফাংশন সংজ্ঞায়িত করুন যা a,b,c,d,e নেবে – প্রতিটি সংখ্যার ডিজিটগুলো রিভার্স করে একটি হ্যাশ তৈরি করবে

• getXY() ফাংশন সংজ্ঞায়িত করুন যা একটি ক্যারেক্টার c নেবে এবং তার (row, col) ফেরত দেবে –

  • a := c - 'A'

  • col := a % 6, row := a / 6

• getDist() ফাংশন সংজ্ঞায়িত করুন যা (a,b) থেকে (c,d) এর ম্যানহ্যাটন দূরত্ব ফেরত দেবে (যদি a,b -1 হয় তবে 0)

• solve() ফাংশন সংজ্ঞায়িত করুন যা x1,y1,x2,y2,word,idx নেবে –

  • যদি idx == word.size() হয়, তবে 0 ফেরত দিন

  • state := getHash(x1+2, y1+2, x2+2, y2+2, idx+2)

  • যদি state memo-তে থাকে, তবে memo[state] ফেরত দিন

  • temp := getXY(word[idx])

  • 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)

  • ans := min(A,B)

  • memo[state] = ans ফেরত দিন

• মূল পদ্ধতিতে 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 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