Computer >> Máy Tính >  >> Lập trình >> C ++

Khoảng cách tối thiểu để gõ một từ bằng hai ngón tay trong C ++

Giả sử chúng ta có bố cục bàn phím như bên dưới -

A B C D E F
G H Tôi J K L
M N O P Q R
S T Ư V W X
Y Z



Trong đó mỗi chữ cái viết hoa tiếng Anh được đặt ở một số tọa độ, chẳng hạn như, chữ A được đặt ở (0,0), chữ B được đặt ở (0,1), chữ P được đặt ở (2,3) và chữ Z được đặt ở (4,1). Bây giờ nếu chúng ta có một từ, chúng ta phải tìm tổng khoảng cách tối thiểu để gõ chuỗi đó chỉ bằng hai ngón tay. Khoảng cách giữa hai nơi (x1, y1) và (x2, y2) là | x1 - x2 | + | y1 - y2 |. Và chúng ta có thể bắt đầu từ bất kỳ vị trí nào trên bàn phím.

Vì vậy, nếu đầu vào giống như "HAPPY", thì đầu ra sẽ là 6, như Bắt đầu bằng H, do đó chi phí là 0, sau đó là A, do đó chi phí từ H đến A là 2, sau đó là P, do đó chi phí bằng 0, sau đó lại P, chi phí là 0, và cuối cùng là Y, do đó chi phí từ P đến Y là 4, do đó tổng chi phí là 6 + 4 =10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một bản ghi nhớ bản đồ

  • Xác định một hàm getHash (), hàm này sẽ nhận a, b, c, d, e,

  • tạm thời:=0

  • trong khi a khác 0, do -

    • temp:=temp * 10 + a mod 10, a:=a / 10

  • trong khi b khác 0, do -

    • temp:=temp * 10 + b mod 10, b:=b / 10

  • trong khi c khác 0, do -

    • temp:=temp * 10 + d mod 10, d:=d / 10

  • trong khi e là khác 0, thực hiện

    • temp:=temp * 10 + e mod 10, e:=e / 10

  • trở lại nhiệt độ

  • Xác định một phương thức getXY (), điều này sẽ mất c

    • Xác định một cặp ret

    • a:=c - ASCII của 'A'

    • ret.second:=a mod 6

    • ret.first:=a / 6

    • trả lại ret

  • Xác định một hàm getDist (), điều này sẽ nhận a, b, c, d,

  • nếu a giống -1 và b giống -1, thì -

    • trả về 0

  • trả về | (b - d) + | a - c ||

  • Xác định một hàm giải quyết (), điều này sẽ nhận x1, y1, x2, y2, word, idx,

  • nếu idx bằng với kích thước của từ, thì -

    • trả về 0

  • trạng thái:=getHash (x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2)

  • nếu trạng thái ở trong bản ghi nhớ thì -

    • trả lại thư báo [trạng thái]

  • Xác định một cặp temp:=getXY (word [idx])

  • ans:=0

  • A:=getDist (x1, y1, temp.first, temp.second + Liberation (temp.first, temp.second, x2, y2, word, idx + 1))

  • B:=getDist (x2, y2, temp.first, temp.second + Expl (x1, y1, temp.first, temp.second, word, idx + 1))

  • ans:=tối thiểu A và B

  • return memo [state] =ans

  • Từ phương thức chính, hãy làm như sau -

  • trả về giải quyết (-1, -1, -1, -1, từ, 0)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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"));
}

Đầu vào 

"HELLO"

Đầu ra 

4