uva592 - Island of Logic

暴力枚举，最多是3的5次方*2.比较麻烦，写了一晚上，调了一上午。

#include <iostream>
#include <cstring>
#include<cstdio>
#include<cstdlib>
#include <string>
#include<algorithm>
#define MARK -2147483647
using namespace std;
char say[55][100];
int n;int isimpo;int renzhong[]={1,2,3};//天使，恶魔，人
int tian[]={1,2};//白天，黑夜
int renshu;int biren[5],bitian;int day[2]={0};int ren[5][3]={0};char name[3][20]={"divine","evil","human"};
int panren[5]={0};
bool judge()
{//for(int ii=0;ii<5;++ii){if(panren[ii])cout<<ii<<biren[ii]<<endl;}cout<<"bitian"<<bitian<<endl;
    int i;
    for(i=0;i<n;++i)
    { // cout<<say[i][3]<<say[i][4]<<"d";
        char shuishuo=say[i][0];
        if(say[i][3]=='I'&&say[i][4]==' ')
        {
            if(say[i][8]=='n')
            {
                if(say[i][12]=='d'&&say[i][13]=='i'){if(biren[shuishuo-'A']==1||biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                else if(say[i][12]=='h'&&say[i][13]=='u'){if((bitian==1&&biren[shuishuo-'A']==3)||biren[shuishuo-'A']==2)return false; }
                else if(say[i][12]=='e'&&say[i][13]=='v'){if(bitian==2&&biren[shuishuo-'A']==3)return false; }
                //else if(say[i][12]=='l'&&say[i][13]=='y'){ return false;}
               // cout<<"F"<<endl;

            }
            else
            {//cout<<"a"<<endl;
                if(say[i][8]=='d'){if(biren[shuishuo-'A']==3&&bitian==1)return false; }
                else if(say[i][8]=='h'){if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                else if(say[i][8]=='e'){if(biren[shuishuo-'A']==1||biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                else if(say[i][8]=='l') return false;
                //cout<<say[i][8]<<endl;
               // cout<<"d"<<endl;
            }
        }
        else if(say[i][3]=='I'&&say[i][4]=='t')
        {
            if(say[i][9]=='d'){if((biren[shuishuo-'A']==1&&bitian==2)||(biren[shuishuo-'A']==2&&bitian==1))return false; }
            else {if((biren[shuishuo-'A']==1&&bitian==1)||(biren[shuishuo-'A']==2&&bitian==2)||(biren[shuishuo-'A']==3))return false; }
        }
        else
        {
            char shuishuo1=say[i][3];
            if(say[i][8]=='n')
            {
                if(say[i][12]=='d')
                {
                    if(biren[shuishuo1-'A']==1){if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                    else {if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                }
                if(say[i][12]=='h')
                {
                    if(biren[shuishuo1-'A']==3){if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                    else {if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                }
                if(say[i][12]=='e')
                {
                    if(biren[shuishuo1-'A']==2){if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                    else {if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                }
                if(say[i][12]=='l')
                {
                    if(biren[shuishuo1-'A']==2||(biren[shuishuo1-'A']==3&&bitian==2)){if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                    else {if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                }
                 //cout<<"Fa"<<endl;
            }
            else
            {
                        if(say[i][8]=='d')
                {
                    if(biren[shuishuo1-'A']==1){if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                    else {if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                }
                if(say[i][8]=='h')
                {
                    if(biren[shuishuo1-'A']==3){if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                    else {if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                }
                if(say[i][8]=='e')
                {
                    if(biren[shuishuo1-'A']==2){if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                    else {if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                }
                if(say[i][8]=='l')
                {
                    if(biren[shuishuo1-'A']==2||(biren[shuishuo1-'A']==3&&bitian==2)){if(biren[shuishuo-'A']==2||(biren[shuishuo-'A']==3&&bitian==2))return false; }
                    else {if(biren[shuishuo-'A']==1||(biren[shuishuo-'A']==3&&bitian==1))return false; }
                }
            }
        }
    }return true;
}
void fuzhi(int i)
{   int j;
    if(i==5)
    {   bitian=1;//白天
    //for(int ii=0;ii<5;++ii){if(panren[ii])cout<<ii<<biren[ii]<<endl;}
        if(judge())
        { isimpo=0;//cout<<"Aaaaaaaaaaaaaaaaaaaaaa"<<endl;
          int ii;//cout<<"b"<<endl;
          for(ii=0;ii<5;++ii)
          {
              if(panren[ii]) ren[ii][biren[ii]-1]=1;
          }
          day[bitian-1 ]=1;
        }
        bitian=2; //黑夜
        if(judge())
        { //cout<<"a"<<endl;
           // cout<<"Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"<<endl;
            isimpo=0;
          int ii;
          for(ii=0;ii<5;++ii)
          {
              if(panren[ii]) ren[ii][biren[ii]-1]=1;
          }
          day[bitian-1 ]=1;
        }
            return;
    }
        if(panren[i]==0){biren[i]=0;fuzhi(i+1);}
        else
        {for(j=0;j<3;++j)
            {biren[i]=renzhong[j];fuzhi(i+1);}
        }
    return;
}
int main()
{
 // freopen("in.txt","r",stdin);
    int ci=1;
    while(scanf("%d",&n))
    {   renshu=0;isimpo=1;
        getchar();
        if(!n)break;
        int i,j;
        memset(panren,0,sizeof(panren));
        for(i=0;i<n;++i)
        {
            gets(say[i]);
//            getchar();
//            cout<<say[i]<<"d"<<endl;
            ++panren[say[i][0]-'A'];
            if(say[i][3]!='I')
            ++panren[say[i][3]-'A' ];
        }
        for(i=0;i<5;++i)if(panren[i])++renshu;
        memset(day,0,sizeof(day));
        memset(ren,0,sizeof(ren));
        fuzhi(0);
       printf("Conversation #%d\n",ci++);
       int flag=0;
        if(isimpo)printf("This is impossible.\n\n");
        else
        {
             for(i=0;i<5;++i)
             {
                 if((ren[i][0]&&!ren[i][1]&&!ren[i][2])){flag=1;printf("%c is %s.\n",(char)(i+'A'),name[0]); }
                 if((ren[i][1]&&!ren[i][0]&&!ren[i][2])){flag=1;printf("%c is %s.\n",(char)(i+'A'),name[1]); }
                 if((ren[i][2]&&!ren[i][0]&&!ren[i][1])){flag=1;printf("%c is %s.\n",(char)(i+'A'),name[2]); }
             }
             if(day[0]&&!day[1]){flag=1;printf("It is day.\n");}
             if(day[1]&&!day[0]){flag=1;printf("It is night.\n");}
             if(!flag)printf("No facts are deducible.\n");
             printf("\n");
        }
    }
    return 0 ;
}

           

 从http://online-judge.uva.es/board/viewtopic.php?f=6&t=2682&p=113439&hilit=592#wrap找到的几组数据

6

A: B is human.

A: B is evil.

B: A is human.

C: A is not lying.

B: C is not human.

D: E is not lying.

4

A: I am human.

A: It is night.

B: I am human.

B: It is day.

3

A: I am human.

B: I am human.

A: B is lying.

3

A: I am divine.

B: A is not lying.

A: B is lying.

3

A: I am divine.

B: A is lying.

A: B is lying.

5

A: B is human.

A: B is evil.

B: A is evil.

C: A is not lying.

B: It is day.

5

C: A is not lying.

A: B is human.

A: B is evil.

B: A is evil.

B: It is day.

1

A: A is not lying.

1

A: A is lying.

2

E: E is evil.

E: E is divine.

7

A: It is night.

B: It is day.

C: I am human.

E: C is human.

C: E is divine.

A: B is lying.

B: C is evil.