HDU 2147 kiki's game：棋盤巴什博弈必勝策略

遊戲規則

n × m 棋盤，棋子初始位於右上角 (1, m)。雙方輪流移動，每步可向左、下、或左下移動一格。無法移動者負（即先走到左下角 (n, 1) 者勝）。kiki 先手，雙方最優策略，求先手勝負。

P-N 圖分析

從終點 (n, 1) 逆向標記：

• P-position（必敗點）：當前玩家必輸的位置
• N-position（必勝點）：當前玩家有移動到 P-position 的策略

繪製小規模棋盤（如 4×4）可觀察規律：

(行,列)  1  2  3  4
1        P  N  P  N
2        N  P  N  P
3        P  N  P  N
4        N  P  N  P

結論：起始點 (1, m) 為 P-position 當且僅當 n 和 m 皆為奇數。反之，只要 n 或 m 有一個是偶數，先手必勝。

數學證明

1. 終點 (n,1)：若 n 為奇數則 P，偶數則 N（但終點固定為 P）
2. 每步移動改變 (row + col) 的奇偶性：
       左/下：和變 ±1 → 奇偶翻轉
       左下：和變 -2 → 奇偶不變
3. 起點 (1, m) 和為 1+m，終點 (n, 1) 和為 n+1
4. 若 n、m 同為奇數，起點和為偶，終點和為偶，先手無法強制進入 P-position
5. 否則先手可移動至某 P-position，掌握主動權

完整代碼（C 語言）

#include <cstdio>

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0) break;
        if (n % 2 == 0 || m % 2 == 0)
            printf("Wonderful!\n");   // 先手勝
        else
            printf("What a pity!\n"); // 先手敗
    }
    return 0;
}

複雜度

• 時間：O(1) 每測試案例
• 空間：O(1)

巴什博弈變體總結