ABC349E Weighted Tic-Tac-Toe

__S08577__ · 2024-04-19 12:53:57 · 题解

感谢@KSCD_

思路

我们发现数据范围非常小，可以用DFS直接解决。

显然，这道题需要回溯。我们设三个参数 st，x，y，分别代表涂色格子数，高桥的总分与青木的总分。

首先我们需要判断前一个操作者有没有连成三个子，如果连成了，返回假。

如果 st==9，就根据总分大小来分胜负。

我们遍历每一个格子，如果这个格子还没有涂过色，就将其涂上现在操作者的颜色。后面dfs即可，注意回溯。

代码

#include<iostream>
using namespace std;
#define int long long
const int N=4;
int a[N][N];
int v[N][N];
int dfs(int st,int x,int y){//x:Takahshi    y:Aoki   的总分
    int xs;//现手
    xs=st%2+1;//如果是1，就是Takashi
    int hs;
    hs=(st+1)%2+1;
    if(v[1][1]==hs&&v[1][2]==hs&&v[1][3]==hs) return 0;
    if(v[2][1]==hs&&v[2][2]==hs&&v[2][3]==hs) return 0;
    if(v[3][1]==hs&&v[3][2]==hs&&v[3][3]==hs) return 0;
    if(v[1][1]==hs&&v[2][2]==hs&&v[3][3]==hs) return 0;
    if(v[1][3]==hs&&v[2][2]==hs&&v[3][1]==hs) return 0;
    if(v[1][1]==hs&&v[2][1]==hs&&v[3][1]==hs) return 0;
    if(v[1][2]==hs&&v[2][2]==hs&&v[3][2]==hs) return 0;
    if(v[1][3]==hs&&v[2][3]==hs&&v[3][3]==hs) return 0;
    //cout<<st;
    if(st==9){//如果格子全部被填满
        if(y<x){
            return 0;
        }
        return 1;
    }

    int f=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(v[i][j]==0){
                v[i][j]=xs;
                if(xs==1){
                    f=dfs(st+1,x+a[i][j],y);
                }
                else{
                    f=dfs(st+1,x,y+a[i][j]);
                }
                v[i][j]=0;
                if(f) return 1;
            }
        }
    }
    return 0;
}
signed main(){
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) cin>>a[i][j];
    if(dfs(0,0,0)) cout<<"Takahashi";
    else cout<<"Aoki";
}