Số Bước Di Chuyển Tối Thiểu Của Mã Trong C++

Giả sử chúng ta có bàn cờ vô hạn với tọa độ từ -vô cực đến +vô cực, và một con mã ở ô [0, 0]. Mã có 8 nước đi có thể như hình dưới. Mỗi nước đi là hai ô theo hướng chính, sau đó một ô theo hướng vuông góc.

Chúng ta phải tìm số bước tối thiểu để di chuyển mã đến ô [x, y]. Đáp án luôn tồn tại.

Ví dụ, x = 5, y = 5, đầu ra là 4. Đường đi: [0,0] → [2,1] → [4,2] → [3,4] → [5,5].

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa map m để lưu kết quả đệ quy (memoization).

• Định nghĩa phương thức solve(x, y):

  • Nếu x + y == 0, trả về 0; nếu x + y == 2, trả về 2.

  • Tạo cặp temp = (x, y).

  • Nếu m có temp, trả về m[temp].

  • Trả về m[temp] = min(solve(|x-1|, |y-2|), solve(|x-2|, |y-1|)) + 1.

• Từ phương thức chính, gọi solve(|x|, |y|) và trả về kết quả.

Ví dụ (C++)

Hãy xem 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));
    }
};

int main(){
    Solution ob;
    cout << (ob.minKnightMoves(5, 5));
}

Đầu vào

5 5

Đầu ra

4