मान लीजिए हमारे पास नीचे जैसा कीबोर्ड लेआउट है:
| A | B | C | D | E | F |
| G | H | I | J | K | L |
| M | N | O | P | Q | R |
| S | T | U | V | W | X |
| Y | Z |
जहां प्रत्येक अंग्रेजी बड़ा अक्षर कुछ निर्देशांक पर स्थित है, उदाहरण के लिए, अक्षर 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