TIOJ 1046 B.陷阱

[爆搜]
:3

#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#define INF 100
#define min(a,b) ((a)>(b)) ? (b):(a)
bool Field[7][7];
bool Test[10][10];
int Rowcnt=0;
int RowLen=0;
int dfs(int x,int y,bool k)
{
    if(x==RowLen+1)
    {
        for(int ly=2;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                Test[ly][lx]=Test[ly-1][lx]^Test[ly-1][lx+1]^Test[ly-1][lx-1]^Test[ly-2][lx]^Field[ly-1][lx];
        for(int ly=1;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                if((Field[ly][lx])!=
                    (Test[ly][lx-1]^Test[ly][lx+1]^Test[ly][lx]^Test[ly-1][lx]^Test[ly+1][lx])) return INF;
        int sum=0;
        for(int ly=1;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                sum+=Test[ly][lx];
        return sum;
    }
    else if(y==1)
    {
        Test[y][x]=k;
        int a=dfs(x+1,y,false);
        int b=dfs(x+1,y,true);
        return min(a,b);
    }
}
int main()
{
    while(1)
    {
        char I[8];gets(I);
        Rowcnt=0;
        if(I[0]=='#')
            break;
        for(int lx=0;I[lx]!='\0';lx++)
            RowLen=lx+1;
        while(strlen(I)>0)
        {
            for(int lx=0;I[lx]!='\0';lx++)
                Field[Rowcnt+1][lx+1]=(I[lx]=='O');
            Rowcnt++;
            gets(I);
        }
        memset(Test,false,sizeof(Test));
        int a=dfs(1,1,false),b=dfs(1,1,true);
        int c=min(a,b);
        if(c>=INF)
            printf("Another Skeleton in the Ancient Tomb!\n");
        else
            printf("Minimum Steps : %d\n",c);
    }
    return 0;
}