TIOJ 1061 井字遊戲(TTT) [ 95北市賽 ] [DFS]

poao899    0K    167MS    G++     0.84K     2009-12-11 15:29:25                                           .

DFS + Hash判重(咦好像不是這樣用

是說co了四次QQ

有兩次在DFS時不printf()會跑不起來超詭異



//*****************************

#include<stdio.h>
short way[8][3]={
    0,1,2,
    3,4,5,
    6,7,8,
    0,3,6,
    1,4,7,
    2,5,8,
    0,4,8,
    2,4,6,
};
short n,st,cnt[3],a[10],o,x,c;
bool H[19683];
bool hash(){
    int h=0;
    for(int i=0;i<9;i++)
        h=h*3+a[i];
    if(H[h])return 1;
    H[h]=1;return 0;
}
int chk(){
    short x;
    for(int i=0;i<8;i++)
        if((x=a[way[i][0]]) == a[way[i][1]] && a[way[i][1]] == a[way[i][2]] && x)
            return x;
    return 0;
}
void dfs(bool pl){
    int b=0,x=chk();
    if(x){
        if(!hash())
            cnt[x]++;
        return;
    }
    for(int i=0;i<9;i++){
        if(a[i]==0){
            a[i]=pl+1;
            dfs(!pl);
            a[i]=0;
            b=1;
        }
    }
    if(!b && !hash())
        cnt[x]++;
}

main(){
    for(int z=0;z<9;z++){
        c=getchar();
        if(c=='O'){o++;a[z]=1;}
        else if(c=='X'){x++;a[z]=2;}
        else a[z]=0;
    }
    dfs(o>x);
    printf("%hd %hd %hd %hd\n",cnt[0]+cnt[1]+cnt[2],cnt[1],cnt[2],cnt[0]);
}