思路分析
由 “两人都是以最优策略行棋” 可知,这是一道博弈题,博弈简单来说就是每个人都会想方设法让自己的得分最优 ,而对于本题,Alice的最优得分越大越好,Bob的最优得分越小越好。 且Alice先下,则可以画出下面的搜索树:
而这种搜索又叫做 最大最小搜索(ab剪枝搜索)
代码如下
#include<bits/stdc++.h>
using namespace std;
const int N = 10, INF = 1e6;
int a[N][N];
bool check(int x)
{
for (int i = 1; i <= 3; i++)
{
int s = 0;
for (int j = 1; j <= 3; j++) //一行是否都是x
{
if (a[i][j] == x)
s++;
}
if (s == 3)
return true;
s = 0;
for (int j = 1; j <= 3; j++) //一列是否都是x
{
if (a[j][i] == x)
s++;
}
if (s == 3)
return true;
}
if (a[1][1] == x && a[2][2] == x && a[3][3] == x) //正对角线
return true;
if (a[1][3] == x && a[2][2] == x && a[3][1] == x) //斜对角线
return true;
return false;
}
int value() //计算得分
{
int s = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
if (!a[i][j])
s++;
}
}
if (check(1)) //如果Alice 获胜
return s + 1;
if (check(2)) //如果Bob 获胜
return -(s + 1);
if (!s) // 注意这里的if条件的顺序,就算没有剩余,也不一定是平局了!! 因为可能最后一步棋Alice 或者Bob获胜了! 所以要把它放到下面。
return 0; //如果平局
return INF; //如果还没这局还没结束
}
int dfs(int x)
{
int v = value();
if (v != INF)
return v;
int res;
if (x == 1) //Alice 要获得最大值
{
res = -INF;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
if (!a[i][j])
{
a[i][j] = 1;
res = max(res, dfs(2));
a[i][j] = 0;
}
}
}
}
else //Bob 要获得最小值
{
res = INF;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
if (!a[i][j])
{
a[i][j] = 2;
res = min(res, dfs(1));
a[i][j] = 0;
}
}
}
}
return res;
}
void solve()
{
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
cin >> a[i][j];
}
}
int ans = dfs(1); //1 表示Alice先下,
cout << ans << '\n';
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}