Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

【注意】最好不要讨论各种情况,预处理所有情况,3进制压缩,共20000个状态

Posted by WilliamACM at 2013-01-22 17:45:42 on Problem 3075
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator