uva 11534 - Say Goodbye to Tic-Tac-Toe(Nim和)

浏览数：24 / 时间：2015年06月12日

题目链接：uva 11534 - Say Goodbye to Tic-Tac-Toe

题目大意：给定一个1*n的个子，每次操作可以选中一个未填过的个子画X或者O，如果该次操作形成了XX或者OO，那么该次操作者视为失败，人为先手，对于给定状态（注意当前状态也算在步数中），问是否可以战胜电脑。

解题思路：对于固定长度，两端的可能有空，X，O，组合情况共有9种，虽然有些情况等价，但是为方便处理，分为9种情况考虑。预先处理出各个长度下9种情况的SG值。然后对于给定状态，枚举位置放X和O，判断新状态的Nim和。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 100;

int s[maxn+5][9];

int SG (int l, int x, int y) {
    int vis[maxn+5];
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= l; i++) {

        if ((i != 1 || x != 1) && (i != l || y != 1)) {
            int X = s[i-1][x*3+1] ^ s[l-i][1*3+y];
            vis[X] = 1;
        }

        if ((i != 1 || x != 2) && (i != l || y != 2)) {
            int O = s[i-1][x*3+2] ^ s[l-i][2*3+y];
            vis[O] = 1;
        }
    }

    int mv = -1;
    while (vis[++mv]);
    return mv;
}

void init (int n) {
    memset(s[0], 0, sizeof(s[0]));

    for (int i = 0; i < 9; i++)
        s[1][i] = 1;
    s[1][1*3+2] = s[1][2*3+1] = 0;


    for (int i = 2; i <= n; i++) {
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++)
                s[i][x*3+y] = SG(i, x, y);
        }
    }
}

char str[maxn+5];

bool judge () {
    int len = strlen(str+1);

    int l = 0, r = 0, cnt = 0, ans = 0, k = 0;
    for (int i = 1; i <= len; i++) {
        if (str[i] == ‘.‘)
            k++;
        else {
            r = (str[i] == ‘X‘ ? 1 : 2);
            ans ^= s[k][l*3+r];
            cnt++;
            l = r;
            k = 0;
        }
    }

    ans ^= s[k][l*3];
    if (cnt&1)
        ans = (ans == 0 ? 1 : 0);
    return ans;
}

int main () {
    init(maxn);
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%s", str+1);
        printf("%s\n", judge() ? "Possible." : "Impossible.");
    }
    return 0;
}