Pro4

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

#include <bits/stdc++.h>

using namespace std;

int save[3][3];

bool raw_ok(int p) 
{
    for(int i = 0; i < 3; ++i)
        if(save[i][0] == save[i][1] && save[i][0] == save[i][2] && save[i][0] == p) return true;
    return false;
}
bool col_ok(int p)
{
    for(int i = 0; i < 3; ++i)
        if(save[0][i] == save[1][i] && save[0][i] == save[2][i] && save[0][i] == p) return true;
    return false;
}
bool dia_ok(int p)
{
    bool flag1 = (save[0][0] == save[1][1] && save[0][0] == save[2][2] && save[0][0] == p);
    bool flag2 = (save[0][2] == save[1][1] && save[0][2] == save[2][0] && save[0][2] == p);
    return flag1 || flag2;
}

bool is_over(int player)
{
    return (raw_ok(player) || col_ok(player) || dia_ok(player));
}

int blank()
{
    int result = 0;
    for(int i = 0; i < 9; ++i) if(save[i/3][i%3] < 0) ++result; 
    return result;
}

int win_count(int player)
{
    int result = blank();
    return !player ? (result + 1) : -(result + 1);
}

int alphabeta(int player, int alpha, int beta)
{
    // printf("alphabeta(%d, %d, %d)\n", player, alpha, beta);
    if(is_over(!player)) return win_count(!player);
    if(blank() == 0) return 0;

    for(int i = 0; i < 9; ++i)
    {
        if(save[i/3][i%3] >= 0) continue;
        save[i/3][i%3] = player;

        int v = alphabeta(player^1, alpha, beta);
        if(!player) alpha = max(alpha, v); else beta = min(beta, v);

        save[i/3][i%3] = -1;
        if(beta <= alpha) break;
    }

    return !player ? alpha : beta;
}

int main(void)
{
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int i = 0; i < T; ++i)
    {
        bool empty = true;
        memset(save, 0, sizeof(save));
        for(int i = 0; i < 9; ++i)
        {
            scanf("%d", &save[i/3][i%3]);
            if(save[i/3][i%3]) empty = false;
            --save[i/3][i%3];
        }
        if(is_over(0)) printf("%d\n", win_count(0));
        else if(is_over(1)) printf("%d\n", win_count(1));
        else if(empty) printf("0\n");
        else printf("%d\n", alphabeta(0, -100, 100));
    }

    return 0;
}