ระยะทางขั้นต่ำในการพิมพ์คำโดยใช้สองนิ้วใน C ++

สมมติว่าเรามีรูปแบบแป้นพิมพ์ด้านล่าง −

ในกรณีที่อักษรตัวพิมพ์ใหญ่ภาษาอังกฤษแต่ละตัวอยู่ที่พิกัดบางตัว เช่น ตัวอักษร A อยู่ที่ (0,0) ตัวอักษร B อยู่ที่ (0,1) ตัวอักษร P จะอยู่ที่ (2,3) และตัวอักษร Z อยู่ที่ (4,1) ทีนี้ ถ้าเรามีคำ เราต้องหาระยะทางรวมขั้นต่ำเพื่อพิมพ์สตริงนั้นโดยใช้เพียงสองนิ้ว ระยะห่างระหว่างสองตำแหน่ง (x1,y1) และ (x2,y2) คือ |x1 - x2| + |y1 - y2|. และเริ่มต้นจากตำแหน่งใดก็ได้บนแป้นพิมพ์

ดังนั้นหากอินพุตเป็นเหมือน "มีความสุข" ผลลัพธ์จะเป็น 6 เมื่อเริ่มต้นด้วย H ดังนั้นต้นทุนจึงเป็น 0 ดังนั้น A ดังนั้นต้นทุนจาก H ถึง A คือ 2 จากนั้น P ดังนั้นต้นทุนจึงเป็น 0 แล้วอีกครั้ง P ต้นทุนเป็น 0 และสุดท้ายคือ Y ดังนั้นต้นทุนจาก P ถึง Y คือ 4 ดังนั้นต้นทุนทั้งหมดคือ 6 + 4 =10

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดบันทึกแผนที่หนึ่งรายการ

• กำหนดฟังก์ชัน getHash() ซึ่งจะใช้ a, b, c, d, e,

• อุณหภูมิ :=0

• ในขณะที่ a ไม่ใช่ศูนย์ ให้ทำ -

  • temp :=temp * 10 + ตัวดัดแปลง 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() ซึ่งจะใช้เวลา c

  • กำหนดหนึ่งคู่ ret

  • a :=c - ASCII ของ 'A'

  • ret.second :=mod 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)

• ถ้า state อยู่ในบันทึกแล้ว −

  • บันทึกการส่งคืน[สถานะ]

• กำหนดหนึ่งคู่ 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))

• ans :=ขั้นต่ำของ A และ B

• บันทึกช่วยจำ[state] =ans

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ผลตอบแทนการแก้ (-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"

ผลลัพธ์

4