POJ 2311 Cutting Game 完整解析

W×H 矩形，雙方輪流沿格線橫切或豎切。率先切出 1×1 格者勝。求先手必勝/必敗。W,H ≤ 200。

核心理論：Grundy 數（SG 函數）

遊戲狀態 = 當前矩形集合。每個矩形獨立構成子遊戲，總 SG 值 = 所有矩形 SG 值異或和。
單個 w×h 矩形的 SG 值：

grundy(w, h) = mex{ grundy(i, h) ⊕ grundy(w-i, h) | 2 ≤ i ≤ w-2 }
                ∪ { grundy(w, j) ⊕ grundy(w, h-j) | 2 ≤ j ≤ h-2 }

切出 1×1 即獲勝，故切割後若任一子矩形為 1×k 或 k×1，該分支直接為終態（SG=0）。遞歸基礎：grundy(w,h)=0 若 w<2 || h<2（無法切割）。

完整 AC 程式碼

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

const int MAX = 256;
int dp[MAX][MAX];

int grundy(int w, int h) {
    if (w < 2 || h < 2) return 0; // 無法切割
    if (dp[w][h] != -1) return dp[w][h];
    
    unordered_set s;
    // 橫切
    for (int i = 2; w - i >= 2; i++)
        s.insert(grundy(i, h) ^ grundy(w - i, h));
    // 豎切
    for (int i = 2; h - i >= 2; i++)
        s.insert(grundy(w, i) ^ grundy(w, h - i));
    
    int g = 0;
    while (s.count(g)) g++;
    return dp[w][h] = g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    memset(dp, -1, sizeof(dp));
    int w, h;
    while (cin >> w >> h) {
        cout << (grundy(w, h) ? "WIN" : "LOSE") << '\n';
    }
    return 0;
}

關鍵點總結

• SG 函數遞歸定義：mex（最小未出現非負整數）
• 切割限制：切後兩塊尺寸均 ≥ 2（否則產生 1×k 直接獲勝，不計入後續博弈）
• 備忘錄優化：dp[256][256] 避免重複計算
• 對稱性：grundy(w,h) = grundy(h,w)，可優化一半狀態
• 複雜度：狀態數 ~200²/2=20000，每狀態 O(W+H) 轉移，總計極快