求当前井字棋局的得分。
用dfs虚构一下搜索树，每个节点对应一个不同的棋局。
每个节点有一个situation()情况评估，若胜负已定，则对应该棋局的评分；否则为0，表示胜负未定或平局。
每个节点还有一个得分用于return，如果situation()值不为0，胜负已定，则节点不再向下拓展，得分即为situation()值；否则若棋盘已满为平局，得分为0，若棋盘未满胜负未定，节点向下拓展，得分需要根据子节点的得分及当前下棋人cur确定。
出题人有一句“当棋盘被填满的时候，游戏结束，双方平手”。Absolutely wrong！棋盘填满不一定平手，一定是先要situation()为0再判断棋盘满不满，以确定是否平手。
#include <bits/stdc++.h>
using namespace std;
struct tNode
{
int chess[9];
tNode()
{
memset(chess, 0, sizeof(chess));
}
tNode(tNode *y)
{
for (int i = 0; i <= 8; i++)
chess[i] = y->chess[i];
}
int remain()
{
int ret = 0;
for (int i = 0; i <= 8; i++)
{
if (chess[i] == 0)
ret ++;
}
return ret;
}
int situation()
{
if (chess[0] == chess[3] && chess[3] == chess[6] && chess[0] != 0)
{
if (chess[0] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[1] == chess[4] && chess[4] == chess[7] && chess[1] != 0)
{
if (chess[1] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[2] == chess[5] && chess[5] == chess[8] && chess[2] != 0)
{
if (chess[2] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[0] == chess[1] && chess[1] == chess[2] && chess[0] != 0)
{
if (chess[0] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[3] == chess[4] && chess[4] == chess[5] && chess[3] != 0)
{
if (chess[3] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[6] == chess[7] && chess[7] == chess[8] && chess[6] != 0)
{
if (chess[6] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[0] == chess[4] && chess[4] == chess[8] && chess[0] != 0)
{
if (chess[0] == 1)
return 1 + remain();
else
return - (1 + remain());
}
if (chess[2] == chess[4] && chess[4] == chess[6] && chess[2] != 0)
{
if (chess[2] == 1)
return 1 + remain();
else
return - (1 + remain());
}
return 0;
}
};
int dfs(tNode *x, int cur)
{
int sit = x->situation();
if (sit != 0)
return sit;
if (x->remain() == 0)
return 0;
int mmax = -20, mmin = 20;
for (int i = 0; i <= 8; i++)
{
if (x->chess[i] == 0)
{
tNode *xx = new tNode(x);
xx->chess[i] = cur;
int temp = dfs(xx, cur % 2 + 1);
mmax = max(mmax, temp);
mmin = min(mmin, temp);
}
}
if (cur == 1)
return mmax;
else
return mmin;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
tNode *st = new tNode();
for (int i = 0; i <= 8; i++)
scanf("%d", &st->chess[i]);
printf("%d\n", dfs(st, 1));
}
return 0;
}