ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1195. Ouths and Crosses

Help ,I got WA on test #11
Posted by HybridTheory 16 Aug 2004 20:13
Who can give me some tests?I've passed all of the tests posted on this board,and I still get WA.Pleas help me.Thank you!!!

This is my program:

#include<iostream>
#include<string>
#include<memory>
using namespace std;

const int win=1;
const int lose=-1;
const int draw=0;
const int maxstatus=20000;
int status[2][maxstatus];
bool visited[2][maxstatus],apd[2][maxstatus];
char map[3][3];
int n=3;

inline int GetID(char x)
{
    switch(x){
        case '#':return 0;
        case 'X':return 1;
        case 'O':return 2;
    }
}

void init()
{
    memset(visited,0,sizeof(visited));
    memset(apd,0,sizeof(apd));
    int i,j;
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            cin>>map[i][j];
        }
    }
}

inline int hash()
{
    int i,j;
    int re=0;
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            re=re*3+GetID(map[i][j]);
        }
    }
    return re;
}

inline void swap(char &a,char &b)
{
    char temp=a;a=b;b=temp;
}

bool check(char x)
{
    if(map[1][1]==x){
        if(map[0][0]==x&&map[2][2]==x)return true;
        if(map[0][1]==x&&map[2][1]==x)return true;
        if(map[1][0]==x&&map[1][2]==x)return true;
        if(map[0][2]==x&&map[2][0]==x)return true;
    }
    else if(map[0][0]==x){
        if(map[0][1]==x&&map[0][2]==x)return true;
        else if(map[1][0]==x&&map[2][0]==x)return true;
    }
    else if(map[2][2]==x){
        if(map[2][1]==x&&map[2][0]==x)return true;
        else if(map[0][2]==x&&map[1][2]==x)return true;
    }
    return false;
}

int ouths();

int cross()
{
    int Max=lose;
    int i,j,k,l,h,t;
    h=hash();
    if(visited[0][h])return status[0][h];
    if(check('X')){
        visited[0][h]=true;
        status[0][h]=win;
        return win;
    }
    if(check('O')){
        visited[0][h]=true;
        status[0][h]=lose;
        return lose;
    }
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            for(k=0;k<n;++k){
                for(l=0;l<n;++l){
                    if(map[k][l]=='X'&&map[i][j]=='#'){
                        swap(map[i][j],map[k][l]);
                        h=hash();
                        if(!apd[0][h]){
                            apd[0][h]=true;
                            t=ouths();
                            apd[0][h]=false;
                            if(t>Max)Max=t;
                        }
                        else if(draw>Max)Max=draw;
                        swap(map[i][j],map[k][l]);
                    }
                }
            }
        }
    }
    h=hash();
    visited[0][h]=true;
    status[0][h]=Max;
    return Max;
}

int ouths()
{
    int i,j,k,l,Min=win,h,t;
    h=hash();
    if(visited[1][h])return status[1][h];
    if(check('O')){
        visited[1][h]=true;
        status[1][h]=lose;
        return lose;
    }
    if(check('X')){
        visited[1][h]=true;
        status[1][h]=win;
        return win;
    }
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            for(k=0;k<n;++k){
                for(l=0;l<n;++l){
                    if(map[k][l]=='O'&&map[i][j]=='#'){
                        swap(map[i][j],map[k][l]);
                        h=hash();
                        if(!apd[1][h]){
                            apd[1][h]=true;
                            t=cross();
                            apd[1][h]=false;
                            if(t<Min)Min=t;
                        }
                        else if(draw<Min)Min=draw;
                        swap(map[i][j],map[k][l]);
                    }
                }
            }
        }
    }
    h=hash();
    visited[1][h]=true;
    status[1][h]=Min;
    return Min;
}

int main(void)
{
    init();
    int t=cross();
    if(t==win)cout<<"Crosses win"<<endl;
    else if(!t)cout<<"Draw"<<endl;
    else cout<<"Ouths win"<<endl;
    return 0;
}