95北市資訊學科能力競賽 井字遊戲 (TTT)
作法:DFS(把所有可能舉出來 並將重複的圖忽略)
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
char x[10]={0};
int win,lose,same,top=0;
char way[800][10]={0};
int check()
{
int a,find=0;
int lineO=0,lineX=0;
for(a=0;a<9;a++) if(x[a]==0) break;
if(a!=9) find=1;
for(a=0;a<9;a=a+3)
{
if(x[a]==1&&x[a+1]==1&&x[a+2]==1)
lineO++;
if(x[a]==2&&x[a+1]==2&&x[a+2]==2)
lineX++;
}
for(a=0;a<3;a++)
{
if(x[a]==1&&x[a+3]==1&&x[a+6]==1)
lineO++;
if(x[a]==2&&x[a+3]==2&&x[a+6]==2)
lineX++;
}
if(x[0]==1&&x[4]==1&&x[8]==1) lineO++;
if(x[2]==1&&x[4]==1&&x[6]==1) lineO++;
if(x[0]==2&&x[4]==2&&x[8]==2) lineX++;
if(x[2]==2&&x[4]==2&&x[6]==2) lineX++;
if(lineO>lineX&&(lineO!=0||lineX!=0)) return 1;/*win++;*/
else if(lineO<lineX&&(lineO!=0||lineX!=0)) return 2;/*lose++;*/
else if(lineO==lineX&&find==0) return 3;/*same++;*/
else return 0;
}
void DFS(int now,int OX)
{
int a,b;
int test=check();
if(test!=0)
{
for(a=0;a<=top;a++)
{
for(b=0;b<9;b++)
if(way[a][b]!=x[b]) break;
if(b==9) break;
}
if(a==top+1)
{
top++;
for(a=0;a<9;a++)
way[top][a]=x[a];
if(test==1) win++;
else if(test==2) lose++;
else same++;
}
return;
}
if(now==9) return;
if(OX==1) /*換 O */
for(a=0;a<9;a++)
{
if(x[a]==0)
{
x[a]=1;
DFS(now+1,2);
x[a]=0;
}
}
if(OX==2) /*換 X */
for(a=0;a<9;a++)
{
if(x[a]==0)
{
x[a]=2;
DFS(now+1,1);
x[a]=0;
}
}
DFS(now+1,OX);
}
main()
{
int a;
while(scanf("%s",x)==1)
{
int X=0,O=0;
for(a=0;a<9;a++)
if(x[a]=='O') {x[a]=1;O++;}
else if(x[a]=='X') {x[a]=2;X++;}
else x[a]=0;
win=0;lose=0;same=0;top=0;
if(O>X) DFS(O+X,2);/*換X*/
else DFS(O+X,1);
printf("%d %d %d %d\n",win+lose+same,win,lose,same);
}
return 0;
}