本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-14 10:26:02

题意

有一个三行三列的网格，每格上有一个数，两人在上面玩井字棋，选到连续三个格子即获胜。若出现平局，则所选格子上的数字和较大者获胜，问谁有必胜策略。

思路

是一道博弈论题，但数据规模很小，一共只有 $9$ 个格子，可以dfs乱搞。

直接暴力dfs搜索两人的选择，分别标记为两人的序号，随时检查是否分出胜负即可。

要注意的是，只要在当前局面下有一种操作能使对方必败，则自己如此操作就必胜；若所有操作方式最终都让对方有必胜策略，则自己必败。

具体请看代码实现。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=3+10;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int a[N][N],v[N][N];\/\/输入的数和每个格子被选的情况 
bool dfs(int st,int x,int y)\/\/已选了st个格子，初始先手的和为x，初始后手的和为y，此时操作是否有必胜策略 
{
	int now=st%2+1,la=(st+1)%2+1;\/\/1为初始先手，2为初始后手；now为现在即将操作的人，la为上一个操作者 
	if(v[1][1]==la&&v[1][2]==la&&v[1][3]==la) return 0;
	if(v[2][1]==la&&v[2][2]==la&&v[2][3]==la) return 0;
	if(v[3][1]==la&&v[3][2]==la&&v[3][3]==la) return 0;
	if(v[1][1]==la&&v[2][2]==la&&v[3][3]==la) return 0;
	if(v[1][3]==la&&v[2][2]==la&&v[3][1]==la) return 0;
	if(v[1][1]==la&&v[2][1]==la&&v[3][1]==la) return 0;
	if(v[1][2]==la&&v[2][2]==la&&v[3][2]==la) return 0;
	if(v[1][3]==la&&v[2][3]==la&&v[3][3]==la) return 0;\/\/判断上一个操作者是否连成三个 
	if(st==9)\/\/若全部选完，则根据大小判断胜负 
	{
		if(x>y) return 0;
		else return 1;\/\/要注意此处st=9，即初始后手即将操作，所以y较大时是必胜 
	}
	for(int i=1;i<=3;i++) for(int j=1;j<=3;j++)
	{
		if(v[i][j]) continue;
		v[i][j]=now;
		bool tf;
		if(now==1) tf=dfs(st+1,x+a[i][j],y);
		else tf=dfs(st+1,x,y+a[i][j]);\/\/分初始先后手判断 
		v[i][j]=0;\/\/注意回溯 
		if(!tf) return true;\/\/对方必败则如此操作可必胜 
	}
	return false;
}
signed main()
{
	for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) a[i][j]=read();
	if(dfs(0,0,0)) cout<<"Takahashi"; 
	else cout<<"Aoki";
	return 0;
}