在C ++中用两个手指键入单词的最小距离
假设我们的键盘布局如下所示-
ACEGIKMOQSUWY
每个英语大写字母位于某个坐标处，例如，字母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+4=10。
为了解决这个问题，我们将遵循以下步骤-
定义一个映射备忘录
定义一个函数getHash()，它将使用a，b，c，d，e，
温度：=0
当a不为零时，请-
temp：=temp*10+一个mod10，a：=a/10
当b不为零时，执行-
温度：=温度*10+bmod10，b：=b/10
当c不为零时，执行-
温度：=温度*10+dmod10，d：=d/10
当e不为零时，
temp：=temp*10+emod10，e：=e/10
返回温度
定义一个方法getXY()，这将花费c
定义一对ret
a：=c-'A'的ASCII
ret.second：=mod6
ret.first：=a/6
返回ret
定义一个函数getDist()，它将使用a，b，c，d，
如果a与-1相同且b与-1相同，则-
返回0
返回|(b-d)+|a-c||
定义一个功能solve()，它将使用x1，y1，x2，y2，word，idx，
如果idx与单词的大小相同，则-
返回0
状态：=getHash（x1+2，y1+2，x2+2，y2+2，idx+2）
如果状态为备忘录，则-
返回备忘录[状态]
定义一对temp：=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））
ans：=A和B的最小值
返回备忘录[state]=ans
从主要方法中执行以下操作-
returnsolve(-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