ความน่าจะเป็นของการเดินของม้าบนกระดานหมากรุกใน C++

กำหนดกระดานหมากรุกขนาด NxN ม้าเริ่มต้นที่แถว r และคอลัมน์ c พยายามเดิน K ครั้ง แถวและคอลัมน์เริ่มจาก 0 (มุมซ้ายบนคือ (0,0) มุมขวาล่างคือ (N-1,N-1))

ม้าเดินได้ 8 ทิศทาง ตามรูปด้านล่าง:

ทุกครั้งที่ม้าเดิน จะเลือก 1 ใน 8 ทิศทางแบบสุ่ม ม้าเดินต่อจนกว่าจะครบ K ครั้งหรือเดินออกนอกกระดาน ต้องการหาความน่าจะเป็นที่ม้าอยู่บนกระดานหลังหยุดเดิน

ตัวอย่าง: input = 3, 2, 0, 0 → output = 0.0625 เพราะมี 2 ทางเดินที่อยู่บนกระดาน จากแต่ละตำแหน่งก็มี 2 ทางเช่นกัน ดังนั้นความน่าจะเป็น = (2/8) × (2/8) = 0.0625

วิธีแก้ปัญหา (Dynamic Programming + Memoization)

1. กำหนดอาร์เรย์ทิศทาง dir = [[-2,-1], [-2,1], [2,-1], [2,1], [1,2], [1,-2], [-1,2], [-1,-2]]
2. สร้างฟังก์ชันเวียนเกิด solve(x, y, n, k, dp):
   • หาก x,y นอกกระดาน → คืน 0
   • หาก k = 0 → คืน 1
   • หาก dp[k][x][y] ≠ -1 → คืนค่าที่เก็บไว้
   • dp[k][x][y] = 0
   • วน i = 0 ถึง 7: dp[k][x][y] += solve(x+dir[i][0], y+dir[i][1], n, k-1, dp)
   • คืน dp[k][x][y]
3. จาก main: สร้าง dp ขนาด (K+1)×N×N เติม -1 แล้วคืน solve(r,c,N,K,dp) / 8^K

ตัวอย่างโค้ด 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;
}

Input

3 2 0 0

Output

0.0625