Xác suất mã ngựa ở lại bàn cờ trong C++

Cho bàn cờ N x N, mã ngựa bắt đầu tại ô (r, c) và thực hiện đúng K nước đi. Mỗi nước đi, mã chọn ngẫu nhiên một trong 8 hướng đi hợp lệ. Tính xác suất mã vẫn còn trên bàn cờ sau K nước.

Ví dụ: N=3, K=2, r=0, c=0 → xác suất 0.0625.

Thuật toán (Đệ quy + Memoization)

1. Mảng hướng đi 8 chiều: dir = {{-2,-1}, {-2,1}, {2,-1}, {2,1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}}.
2. Hàm solve(x, y, n, k, dp):
   • Nếu ngoài bàn cờ → trả về 0.
   • Nếu k == 0 → trả về 1.
   • Nếu dp[k][x][y] != -1 → trả về giá trị đã lưu.
   • Khởi tạo dp[k][x][y] = 0, duyệt 8 hướng, cộng dồn xác suất từ trạng thái k-1.
3. Từ hàm chính: khởi tạo mảng 3D dp(K+1, N, N, -1), gọi solve(r, c, N, K, dp) / 8^K.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int dir[8][2] = {{-2,-1}, {-2,1}, {2,-1}, {2,1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};

class Solution {
public:
    double solve(int x, int y, int n, int k, vector<vector<vector<double>>>& dp) {
        if (x >= n || y >= n || x < 0 || y < 0) return 0.0;
        if (k == 0) return 1.0;
        if (dp[k][x][y] != -1) return dp[k][x][y];
        dp[k][x][y] = 0;
        for (int i = 0; i < 8; i++) {
            dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k-1, dp);
        }
        return dp[k][x][y];
    }
    double knightProbability(int N, int K, int r, int c) {
        vector<vector<vector<double>>> dp(K+1, vector<vector<double>>(N, vector<double>(N, -1)));
        return solve(r, c, N, K, dp) / pow(8, K);
    }
};

int main() {
    Solution ob;
    cout << ob.knightProbability(3, 2, 0, 0);
    return 0;
}

Đầu vào / Đầu ra

Input: 3 2 0 0

Output: 0.0625