您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 4832 Chess 解題：國王移動計數 DP + 組合數學

編輯：C++ 入門

問題描述

N×M 棋盤，國王從 (x,y) 起始，恰好走 K 步 (每步可走周圍 8 格或原地？不，國王必須移動到相鄰 8 格)，不走出棋盤，最終回到起點的路徑數。模 9999991。

核心洞察：水平/垂直獨立 + 組合合併

國王移動可分解為：

水平移動：左/右/不動 (對應 x 軸 -1/0/+1)
垂直移動：上/下/不動 (對應 y 軸 -1/0/+1)
但注意：國王每步**必須移動**，即 (dx,dy) ≠ (0,0)。水平和垂直步數之和 = K。

動態規劃：單軸移動計數

定義 dp[step][pos] = 走 step 步後在相對位置 pos 的方案數。
位置編碼：pos = offset + k，offset = K，範圍 [-K, K]。

轉移方程

// 水平 DP (垂直同理)
dp[0][offset + x] = 1;  // 起始位置 x (1-based)

for (int s = 1; s <= K; ++s) {
    for (int p = -K; p <= K; ++p) {
        int idx = offset + p;
        if (dp[s-1][idx] == 0) continue;
        // 三種移動：左(-1)、不動(0)、右(+1) -- 但國王必須移動！
        // 實際上國王水平分量可為 -1,0,1，垂直分量同理
        // 這裡計算單軸獨立移動，後續組合時排除 (0,0)
        if (p > 1) dp[s][idx-1] = (dp[s][idx-1] + dp[s-1][idx]) % MOD;  // 左移
        if (p < M) dp[s][idx+1] = (dp[s][idx+1] + dp[s-1][idx]) % MOD;  // 右移
        // 注意邊界：p=1 不能左移，p=M 不能右移
    }
}

邊界處理細節

棋盤大小限制：水平位置 ∈ [1, M]，垂直位置 ∈ [1, N]。
DP 陣列大小：[K+1][2K+3] 覆蓋所有可能相對位移。

組合合併：水平 i 步、垂直 K-i 步

設 h[i] = 水平走 i 步不出界的方案數 (所有合法終點位置之和)
v[j] = 垂直走 j 步不出界的方案數

總方案數：

ans = Σ(i=0..K) h[i] * v[K-i] * C(K, i)  (mod MOD)

為什麼乘 C(K,i)？ K 步中選 i 步作水平移動 (其餘 K-i 步作垂直)，步驟順序不同視為不同路徑。

完整 C++ 實作

#include 
#include 
#include 
using namespace std;

typedef long long ll;
const ll MOD = 9999991;
const int MAXK = 1005;

int n, m, k, x, y;
ll h[MAXK], v[MAXK];
ll dp[2][2*MAXK];  // 滾動陣列優化空間
ll C[MAXK][MAXK];

void computeAxis(ll *res, int startPos, int limit, int K) {
    // res[i] = 走 i 步不出界方案數
    memset(dp, 0, sizeof(dp));
    int offset = K;
    dp[0][offset + startPos] = 1;
    res[0] = 1;
    
    for (int s = 1; s <= K; ++s) {
        int cur = s & 1, pre = 1 - cur;
        memset(dp[cur], 0, sizeof(dp[cur]));
        int minPos = max(1, startPos - s);
        int maxPos = min(limit, startPos + s);
        
        for (int p = minPos; p <= maxPos; ++p) {
            int idx = offset + p;
            ll ways = 0;
            // 從左、右、原地 (但國王必須移動！)
            // 此處計算單軸投影移動：每步可 -1, 0, +1
            if (p > 1) ways = (ways + dp[pre][idx-1]) % MOD;
            if (p < limit) ways = (ways + dp[pre][idx+1]) % MOD;
            // 注意：單軸投影允許「水平不動」(0)，對應垂直移動
            ways = (ways + dp[pre][idx]) % MOD;  // 水平分量為 0
            
            dp[cur][idx] = ways;
            res[s] = (res[s] + ways) % MOD;
        }
    }
}

int main() {
    // 預計算組合數
    for (int i = 0; i < MAXK; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
    
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
        memset(h, 0, sizeof(h));
        memset(v, 0, sizeof(v));
        
        computeAxis(h, y, m, k);  // 水平：起始 y，限制 m
        computeAxis(v, x, n, k);  // 垂直：起始 x，限制 n
        
        ll ans = 0;
        for (int i = 0; i <= k; ++i) {
            ans = (ans + h[i] * v[k-i] % MOD * C[k][i]) % MOD;
        }
        
        printf("Case #%d:\n%lld\n", cas, ans);
    }
    return 0;
}