poj4051Chess:搜索

思路：记输、平局、赢得状态分别为-1，0，1.

则有，

先手想要达到某种状态t，如果先手走一步棋子后对手无论怎么走都会达到状态1-t。

后手无论怎么走都会打到状态t，如果下一步无论怎么走先手都会达到状态1-t。

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

int chess[6][6], token, row[2][4], coj[2][4], diag[2][2];

// i,j 位置被id占据后更新状态
void update_state(int i, int j, int id, int add) {
    chess[i][j] = add==1? id:-1;
    row[id][i] += add;
    coj[id][j] += add;
    if (i == j) diag[id][0] += add;
    if (i + j == 3) diag[id][1] += add;
    token += add;
}

int must_get(int t, int id);

int calc_state(int i, int j, int id) {// id占据ij位置后的状态
    if (row[id][i] == 4 || coj[id][j] == 4 ||
        diag[id][0] == 4 || diag[id][1]== 4) return 1;// win
    if (token == 16) return 0;// tie
    return -2;// unkown state
}

int can_get(int t, int id) {// id 能够是否到达状态t
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (chess[i][j] == -1) {
                update_state(i, j, id, 1);
                int stat = calc_state(i, j, id);// 返回ij位置被id占据后的状态
                if (stat == t) {
                    update_state(i, j, id, -1); 
                    return 1;
                }
                if (stat == -2 && must_get(-t, 1 - id)) {
                    update_state(i, j, id, -1);
                    return 1;
                }
                update_state(i, j, id, -1);
            }
        }
    }
    return 0;
}
int must_get(int t, int id) {// 是否id无论怎么走都到达状态t
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (chess[i][j] == -1)     {
                update_state(i, j, id, 1);
                int stat = calc_state(i, j, id);
                if (stat >= 0 && stat != t) {
                    update_state(i, j, id, -1);
                    return 0;
                }
                else if (stat == -2 && !can_get(-t, 1 - id)){
                    update_state(i, j, id, -1);
                    return 0;
                }
                update_state(i, j, id, -1);
            }
        }
    }
    return 1;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int t, tar;
    char c, s[10];
    scanf("%d", &t);
    while (t--) {
        token = 0;
        memset(chess, -1, sizeof(chess));
        memset(row, 0, sizeof(row));
        memset(coj, 0, sizeof(coj));
        memset(diag, 0, sizeof(diag));
        scanf("%s%*[
]", s);
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                scanf("%c", &c);
                if (c == 'x') {// x is 0
                    update_state(i, j, 0, 1);
                }
                else if (c == 'o') {// o is 1
                    update_state(i, j, 1, 1);
                }
            }
            scanf("%*[
]");
        }
        switch (s[0]) {
        case 'L': tar = -1; break;
        case 'W': tar = 1; break;
        default: tar = 0; break;
        }
        if (can_get(tar, token%2))// 先手的id:token%2
            printf("YES
");
        else printf("NO
");
    }
}