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