C++에서 두 손가락을 사용하여 단어를 입력하는 최소 거리

<시간/>

아래와 같은 키보드 레이아웃이 있다고 가정합니다. -

A	나	C	디	이	F
지	ㅎ	나	제	케이	엘
남	N	오	피	질문	R
S	티	U	V	여	X
예	Z

각 영문 대문자가 어떤 좌표에 위치하는 경우, 예를 들어 문자 A는 (0,0)에, 문자 B는 (0,1)에, 문자 P는 (2,3)에 배치됩니다. 문자 Z는 (4,1)에 배치됩니다. 이제 단어가 있는 경우 두 손가락만 사용하여 이러한 문자열을 입력할 수 있는 최소 총 거리를 찾아야 합니다. 두 위치 (x1,y1)과 (x2,y2) 사이의 거리는 |x1 - x2| + |y1 - y2|. 그리고 키보드의 어느 위치에서나 시작할 수 있습니다.

따라서 입력이 "HAPPY"와 같으면 출력은 H로 시작하므로 비용은 0, A, 따라서 H에서 A까지의 비용은 2, 그 다음 P이므로 비용은 0이 되고 다시 6이 됩니다. P, 비용은 0, 마지막으로 Y이므로 P에서 Y까지의 비용은 4이므로 총 비용은 6 + 4 =10입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 지도 메모 정의
getHash() 함수를 정의하면 a, b, c, d, e,
가 필요합니다.
온도 :=0
a가 0이 아닌 동안 −
- temp :=temp * 10 + 모드 10, a :=a / 10
b가 0이 아닌 동안 수행 -
- 온도 :=온도 * 10 + b 모드 10, b :=b / 10
c가 0이 아닌 동안 수행 -
- temp :=temp * 10 + d mod 10, d :=d / 10
e가 0이 아닌 동안 수행
- 온도 :=온도 * 10 + 전자 모드 10, 전자 :=전자 / 10
반환 온도
하나의 메소드 getXY()를 정의합니다. 이것은 c
가 걸립니다.
- 한 쌍의 ret 정의
- a :=c - 'A'의 ASCII
- ret.second :=모드 6
- ret.first :=a / 6
- 리턴 렛
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))
as :=A와 B의 최소값
반환 메모[상태] =as
주요 방법에서 다음을 수행하십시오 -
해결 반환(-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"