อัศวินขั้นต่ำย้ายใน C ++

สมมติว่าเรามีกระดานหมากรุกที่ไม่มีที่สิ้นสุดพร้อมพิกัดจาก -infinity ถึง +infinity และเรามีอัศวินอยู่ที่จัตุรัส [0, 0] อัศวินสามารถเคลื่อนไหวได้ 8 ท่าดังที่แสดงด้านล่าง การเคลื่อนไหวแต่ละครั้งคือสองช่องสี่เหลี่ยมในทิศทางที่สำคัญ จากนั้นหนึ่งช่องในทิศทางตั้งฉาก

เราต้องหาจำนวนขั้นขั้นต่ำที่จำเป็นในการเคลื่อนย้ายอัศวินไปยังช่องสี่เหลี่ยม [x, y] รับรองว่าคำตอบมีอยู่จริง

ดังนั้นหากอินพุตเป็นเหมือน x =5 และ y =5 ผลลัพธ์จะเป็น 4 นี่จะเป็น [0,0] → [2,1] → [4,2] → [3,4] → [ 5,5]

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

• กำหนดแผนที่ ม

• กำหนดวิธีการที่เรียกว่าsol() ซึ่งจะใช้ x และ y

• ถ้า x + y =0 ให้คืนค่า 0 ถ้า x + y =2 ให้คืนค่า 2

• สร้างอุณหภูมิคู่โดยใช้ (x, y)

• ถ้า m มีคู่ temp ให้คืนค่า m[temp]

• คืนค่า m[temp] :=นาทีของการแก้ปัญหา (|x - 1|, |y - 2|)), [solve(|x - 2|, |y - 1|)) + 1]

• จากวิธีหลัก เรียก Solve(|x|, |y|) แล้วคืนค่า

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   map < pair <int, int>, int > dp;
   int solve(int x, int y){
      if(x + y == 0) return 0;
      if (x + y == 2) return 2;
      pair <int, int> temp({x, y});
      if(dp.count(temp)) return dp[temp];
      return dp[temp] = min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1))) + 1;
   }
   int minKnightMoves(int x, int y) {
      return solve(abs(x), abs(y));
   }
};
main(){
   Solution ob;
   cout << (ob.minKnightMoves(5, 5));
}

อินพุต

5
5

ผลลัพธ์

4