深度优先搜索

Solution 1：搜出所有可能的局面，如果给定的局面未被搜索到则非法，其余情况能够轻易判断。

由于状态总数固定，时间复杂度 $O(1)$。

#include<bits/stdc++.h>
using namespace std;
char m[5][5],s[5][5];
bool emp;
inline bool found(){
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(m[i][j]!=s[i][j]) return 0;
    return 1;
}
inline bool check(char x){
    for(int i=1;i<=3;i++){
        bool ret=1;
        for(int j=1;j<=3;j++) if(m[i][j]!=x) ret=0;
        if(ret) return 1;
    }
    for(int i=1;i<=3;i++){
        bool ret=1;
        for(int j=1;j<=3;j++) if(m[j][i]!=x) ret=0;
        if(ret) return 1;
    }
    if(m[1][1]==x&&m[2][2]==x&&m[3][3]==x) return 1;
    if(m[1][3]==x&&m[2][2]==x&&m[3][1]==x) return 1;
    return 0;
}
inline char ex(char x){return x=='X' ? '0':'X';}
void dfs(char now){
    if(found()){//找到给定局面
        if(check(ex(now))){//出现获胜者
            if(ex(now)=='X') puts("the first player won");
            else puts("the second player won");
        }
        else if(emp){//有空位 要么可以继续 要么出现获胜者(已经判断)
            if(now=='X') puts("first");
            else puts("second");
        }
        else puts("draw");//否则平局
        exit(0);
    }
    if(check(ex(now))) return;
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(m[i][j]=='.')
        m[i][j]=now,dfs(ex(now)),m[i][j]='.';
}
int main(){
    for(int i=1;i<=3;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++)
        if(s[i][j]=='.') emp=1;
    memset(m,'.',sizeof(m));
    dfs('X');
    puts("illegal");
    return 0;
}

Solution 2：直接上一大堆判断。

下面是很久前的代码，正确与否和什么意思都忘了，但是它能过题。

#include<bits/stdc++.h>
using namespace std;
int X,H,L,winA,winB,sumA,sumB;
char s[4][4];
int main(){
    for(int i=1;i<=3;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=3;i++){
        if(s[i][1]==s[i][2]&&s[i][2]==s[i][3]){
            if(s[i][1]=='X') winA++,H++;
            if(s[i][1]=='0') winB++,H++;
        }
        if(s[1][i]==s[2][i]&&s[2][i]==s[3][i]){
            if(s[1][i]=='X') winA++,L++;
            if(s[1][i]=='0') winB++,L++;
        }
        for(int j=1;j<=3;j++){
            if(s[i][j]=='X') sumA++;
            if(s[i][j]=='0') sumB++;
        }
    }
    if(s[1][1]==s[2][2]&&s[2][2]==s[3][3]){
        if(s[1][1]=='X') winA++,X++;
        if(s[1][1]=='0') winB++,X++;
    }
    if(s[1][3]==s[2][2]&&s[2][2]==s[3][1]){
        if(s[1][3]=='X') winA++,X++;
        if(s[1][3]=='0') winB++,X++;
    }
    if(winA+winB>=3||winA+winB==2&&(!(H==1&&L==1)&&X!=2&&!(H==1&&X==1)&&!(L==1&&X==1))||sumA<sumB||sumA>=sumB+2||winA&&sumA==sumB||winB&&sumA>sumB) puts("illegal");
    else if(winA) puts("the first player won");
    else if(winB) puts("the second player won");
    else if(sumA+sumB==9) puts("draw");
    else puts(sumA==sumB ? "first":"second");
    return 0;
}