最開始學博弈論的時候學到過博弈論里的一個基本定理

1.當前局面先手必勝當且僅當后續局面存在先手必敗

2.當前局面先手必敗當且僅當后續局面全是先手必勝

當時就想著用搜索做，但是局面太多了搜不過來，所以后面又學了SG函數啥的。

但是這個題很明顯可以搜索。

#include<bits/stdc++.h>
#define int long long
#define ULL unsigned long long
#define DB double
using namespace std;
int n,l,r,cnt;
int a[5][5],se[5][5];
int ying(int s) // 看看是不是s連成三個
{
	if(se[1][1]==s&&se[2][2]==s&&se[3][3]==s)return 1;
	if(se[3][1]==s&&se[2][2]==s&&se[1][3]==s)return 1;
	
	if(se[1][1]==s&&se[1][2]==s&&se[1][3]==s)return 1;
	if(se[2][1]==s&&se[2][2]==s&&se[2][3]==s)return 1;
	if(se[3][1]==s&&se[3][2]==s&&se[3][3]==s)return 1;
	
	if(se[1][1]==s&&se[2][1]==s&&se[3][1]==s)return 1;
	if(se[1][2]==s&&se[2][2]==s&&se[3][2]==s)return 1;
	if(se[1][3]==s&&se[2][3]==s&&se[3][3]==s)return 1;
	return 0;
}
int check() // 看看是否沒有連成三個
{
	if(ying(1))return 1;
	if(ying(2))return 2;
	return 0;
}
int sum(int x) // 沒有連成三個就算一下得分的和
{
	int res=0;
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)
			if(se[i][j]==x)res+=a[i][j];
	return res;
}
int dfs(int bu,int ren) // 現在是第幾步，哪個人先手
{
	if(check()!=0)
	{
		return check()==ren;
	}
	if(bu==10)
	{
		if(sum(2)>sum(1))return 1;
		else return 0;
	}
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)
			if(se[i][j]==0)
			{
				se[i][j]=ren;
				if(dfs(bu+1,3-ren)==0)
				{
					se[i][j]=0;
					return 1;
				}
				se[i][j]=0;
			}
	return 0;
}
signed main()
{
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)cin>>a[i][j];
	if(dfs(1,1))printf("Takahashi");
	else printf("Aoki");
	return 0;
} 
/*
-1 1 0
-4 2000 -5
-4 -1 -5



*/