ระยะทางพิมพ์คำต่ำสุดด้วยสองนิ้วใน C++

คำอธิบายโจทย์

แป้นพิมพ์ 6×5 ตัวอักษร A-Z พิกัด A=(0,0), B=(0,1)... Z=(4,1) ระยะทาง = Manhattan distance หาระยะทางรวมน้อยที่สุดพิมพ์คำด้วย 2 นิ้ว เริ่มที่ไหนก็ได้

ตัวอย่าง

"HAPPY" → Output: 6 (ในโค้ดทดสอบ "HELLO" ได้ 4)

วิธีแก้ปัญหา

ใช้ DP + Memoization (Top-down):

• State: (x1,y1,x2,y2,idx) = ตำแหน่งนิ้ว 1, นิ้ว 2, ตัวอักษรที่ idx
• Hash state เป็น int เก็บใน map
• Transition: พิมพ์ตัวถัดไปด้วยนิ้ว 1 หรือ นิ้ว 2 เลือกค่าน้อยกว่า
• Base case: idx == word.length() → 0
• getXY: แปลง char เป็นพิกัด (row = (c-'A')/6, col = (c-'A')%6)

การทำงานของโค้ด

#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) {
        int a = c - 'A';
        return {a/6, a%6};
    }
    
    int getDist(int a, int b, int c, int d) {
        if(a==-1 && b==-1) return 0;
        return abs(a-c) + abs(b-d);
    }
    
    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.count(state)) return memo[state];
        
        auto 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);
        
        return memo[state] = min(A, B);
    }
    
    int minimumDistance(string word) {
        memo.clear();
        return solve(-1, -1, -1, -1, word, 0);
    }
};

int main() {
    Solution ob;
    cout << ob.minimumDistance("HELLO");
    return 0;
}

อินพุต

"HELLO"

เอาต์พุต

4