Hiệp sĩ tối thiểu di chuyển trong C ++

Giả sử chúng ta có một bàn cờ vô hạn với tọa độ từ -infinity đến + infinity và chúng ta có một quân mã tại hình vuông [0, 0]. Một hiệp sĩ có 8 nước đi có thể thực hiện, như hình dưới đây. Mỗi bước di chuyển là hai hình vuông theo hướng chính yếu, sau đó là một hình vuông theo hướng trực giao.

Chúng ta phải tìm số bước tối thiểu cần thiết để di chuyển kỵ sĩ đến hình vuông [x, y]. Nó được đảm bảo rằng câu trả lời tồn tại.

Vì vậy, nếu đầu vào giống như x =5 và y =5, thì đầu ra sẽ là 4. Điều này sẽ giống như [0,0] → [2,1] → [4,2] → [3,4] → [ 5,5]

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

• Xác định bản đồ m

• xác định một phương thức được gọi là giải quyết (), điều này sẽ nhận x và y

• nếu x + y =0 thì trả về 0, nếu x + y =2 thì trả về 2

• tạo một cặp tạm thời bằng cách sử dụng (x, y)

• nếu m có tạm thời của cặp thì trả về m [temp]

• return m [temp]:=min của giải (| x - 1 |, | y - 2 |)), [giải (| x - 2 |, | y - 1 |)) + 1]

• Từ phương thức chính, gọi giải quyết (| x |, | y |) và trả về giá trị của nó

Ví dụ (C ++)

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

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

Đầu vào

5
5

Đầu ra

4