ABC349E 题解

· · 题解

题意

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

思路

是一道博弈论题，但数据规模很小，一共只有 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;
}