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

UVA 10561 Treblecross：Nim 遊戲與 SG 函數

編輯：C++ 入門

問題描述

長度 n 的棋盤，部分格子已有 'X'。雙方輪流在空格放 'X'，若形成連續 3 個 'X' 獲勝。給定局面，判斷先手是否必勝，若必勝輸出所有獲勝首著位置。

SG 函數分析

放一個 'X' 會禁用其左右兩格（因為會形成 XX. .XX X.X 讓對手必勝）。因此一個 'X' 將棋盤分割為獨立的左右兩段，每段長度減去邊界影響：

左段長度 = i - 3（位置 i 左側）
右段長度 = n - i - 2（位置 i 右側）

SG 函數遞推：g[len] = mex{ g[left] ^ g[right] }，其中 left + right = len - 3（或類似）。預計算 g[1..200]。

局面分解

掃描原串，連續 'X' 之間的空段長度 L，其 SG 值為 g[max(L-4, 0)]（邊界修正）。所有段 SG 值異或 = 0 為必敗態，≠0 為必勝態。

枚舉獲勝首著

對每個 '.'，暫置 'X'，重新計算整個局面 SG 值，若變為 0 則為獲勝著。特殊情況：一步直接形成 XXX 也算獲勝（需單獨檢查）。

參考代碼（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 200;
int g[MAXN+5], vis[MAXN+5];

int SG(int len) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= len; i++) {
        int val = 0;
        if (len - i - 2 >= 0) val ^= g[len-i-2];
        if (i - 3 >= 0) val ^= g[i-3];
        vis[val] = 1;
    }
    int mex = 0;
    while (vis[mex]) mex++;
    return mex;
}

void init() {
    g[1] = g[2] = g[3] = 1;
    for (int i = 4; i <= 200; i++) g[i] = SG(i);
}

bool check(const char *s, int len) { // 判斷局面 SG=0
    int pre = -3, xor_sum = 0;
    for (int i = 0; i <= len; i++) {
        if (i == len || s[i] == 'X') {
            if (i - pre <= 2) return false; // 已有 XXX
            int L = max(i - pre - 5, 0);
            if (L) xor_sum ^= g[L];
            pre = i;
        }
    }
    int L = max(len - pre - 3, 0);
    if (L) xor_sum ^= g[L];
    return xor_sum == 0;
}

int main() {
    init();
    int T; scanf("%d", &T);
    while (T--) {
        char s[MAXN+5]; scanf("%s", s);
        int len = strlen(s);
        int pos[MAXN], cnt = 0;
        for (int i = 0; i < len; i++) if (s[i] == '.') {
            s[i] = 'X';
            if (check(s, len)) pos[cnt++] = i+1;
            s[i] = '.';
            // 一步直接勝
            if (i && i < len-1 && s[i-1]=='X' && s[i+1]=='X') pos[cnt++] = i+1;
            if (i < len-2 && s[i+1]=='X' && s[i+2]=='X') pos[cnt++] = i+1;
            if (i >= 2 && s[i-1]=='X' && s[i-2]=='X') pos[cnt++] = i+1;
        }
        if (cnt) {
            puts("WINNING");
            for (int i = 0; i < cnt; i++)
                printf("%d%c", pos[i], i==cnt-1?'\n':' ');
        } else puts("LOSING");
    }
    return 0;
}