Khoảng cách tối thiểu gõ từ dùng hai ngón tay trong C++

Cho bố trí bàn phím 6x5 (A-Z). Mỗi chữ cái tại tọa độ: A(0,0), B(0,1), P(2,3), Z(4,1). Khoảng cách Manhattan giữa (x1,y1) và (x2,y2) là |x1-x2|+|y1-y2|. Cho một từ, tìm tổng khoảng cách tối thiểu để gõ dùng 2 ngón tay (có thể bắt đầu ở bất kỳ vị trí nào).

Ví dụ: "HAPPY" → 6. Bắt đầu H (chi phí 0), A (H→A = 2), P (0), P (0), Y (P→Y = 4). Tổng = 6.

Giải pháp

Sử dụng DP với memoization (top-down):

• Trạng thái: (x1,y1,x2,y2,idx) - vị trí 2 ngón tay và chỉ số ký tự đang gõ
• Hàm getXY(c): chuyển ký tự thành tọa độ (row = (c-'A')/6, col = (c-'A')%6)
• Hàm getDist: khoảng cách Manhattan, trả về 0 nếu ngón tay chưa dùng (-1,-1)
• Hàm solve(x1,y1,x2,y2,word,idx):
  • Nếu idx == word.length(): trả về 0
  • Tạo hash trạng thái, kiểm tra memo
  • Lấy tọa độ ký tự hiện tại
  • Chọn ngón tay 1: cost = getDist(x1,y1,tx,ty) + solve(tx,ty,x2,y2,word,idx+1)
  • Chọn ngón tay 2: cost = getDist(x2,y2,tx,ty) + solve(x1,y1,tx,ty,word,idx+1)
  • Lấy min, lưu memo, trả về
• Khởi tạo: solve(-1,-1,-1,-1,word,0)

Ví dụ mã C++

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

Đầu vào

"HELLO"

Đầu ra

4