C++で2本の指を使用して単語を入力するための最小距離

以下のようなキーボードレイアウトがあるとします-

英語の各大文字が特定の座標に配置されている場合、例として、文字Aは（0,0）に配置され、文字Bは（0,1）に配置され、文字Pは（2,3）に配置されます。文字Zは（4,1）に配置されます。ここで単語がある場合、2本の指だけを使用してそのような文字列を入力するための最小合計距離を見つける必要があります。 2つの場所（x1、y1）と（x2、y2）の間の距離は|x1-x2|です。 + |y1-y2|。また、キーボードのどの位置からでも開始できます。

したがって、入力が「HAPPY」の場合、出力は6になります。これは、Start with Hであるため、コストは0、次にAであるため、HからAへのコストは2、次にPであるため、コストは0になります。 P、コストは0、最後にYなので、PからYまでのコストは4なので、合計コストは6 + 4=10です。

これを解決するには、次の手順に従います-

• 1つのマップメモを定義する

• 関数getHash（）を定義します。これには、a、b、c、d、e、

  が必要です。

• temp：=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（）メソッドを1つ定義します。これには、c

  が必要です。

  • 1つのペアを定義するret

  • a：=c-'A'のASCII

  • ret.second：=mod 6

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

• 状態がメモにある場合-

  • メモを返す[状態]

• 1つのペアを定義しますtemp：=getXY（word [idx]）

• ans：=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の最小値

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