| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
【注意】最好不要讨论各种情况,预处理所有情况,3进制压缩,共20000个状态#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int a[3][3];
int vis[20000];
int check(int v)
{
if(a[0][0]==v&&a[0][1]==v&&a[0][2]==v) return 1;
if(a[1][0]==v&&a[1][1]==v&&a[1][2]==v) return 1;
if(a[2][0]==v&&a[2][1]==v&&a[2][2]==v) return 1;
if(a[0][0]==v&&a[1][0]==v&&a[2][0]==v) return 1;
if(a[0][1]==v&&a[1][1]==v&&a[2][1]==v) return 1;
if(a[0][2]==v&&a[1][2]==v&&a[2][2]==v) return 1;
if(a[0][0]==v&&a[1][1]==v&&a[2][2]==v) return 1;
if(a[0][2]==v&&a[1][1]==v&&a[2][0]==v) return 1;
return 0;
}
int init()
{
int t=1;
int ans=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
int v=(a[i][j]!=-1)?a[i][j]:2;
ans+=v*t;
t*=3;
}
return ans;
}
void dfs(int h,int v)
{
if(h==9)
{
vis[init()]=1;return ;
}
if(check(v^1)) {vis[init()]=1;return;}
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(a[i][j]==-1)
{
a[i][j]=v;
dfs(h+1,v^1);
a[i][j]=-1;
}
}
void pre()
{
memset(a,-1,sizeof(a));
dfs(0,1);
}
int main()
{
//freopen("in.txt","r",stdin);
pre();
char s[12];
while(scanf("%s",s),s[0]!='e')
{
memset(a,-1,sizeof(a));
for(int i=0;i<9;i++)
if(s[i]!='.')
a[i/3][i%3]=s[i]=='O'?0:1;
printf("%svalid\n",vis[init()]?"":"in");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator