ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1195. Крестики-нолики

HybridTheory Help ,I got WA on test #11 // Задача 1195. Крестики-нолики 16 авг 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;
}