反転将棋

Description

反転碁の盤には64個の駒があり、8に並んでいる.×8の行列.各駒の表裏両面はそれぞれ白と黒に塗られている.初期状態では,一部の駒は正面を上(白)にし,残りは背面を上(黒)にする.任意の駒を反転させると同時に、隣接する上下左右の4つの駒も一緒に反転しなければなりません.碁盤の初期状態が与えられ、すべての駒の黒い面を上にするには、少なくとも何回反転操作を行う必要があるかをプログラミングして計算します.

Input

入力された最初の行は正の整数Nであり、N組の入力データを表す.各グループのデータには8が含まれています.×8の行列は碁盤の初期状態を表し、‘0’は白を表し、‘1’は黒を表す.2つのデータのセットは空白の行で区切られています.

Output

入力データのセットごとに「Case#:n」の行を出力します.ここで,#’はこのセットから出力されるシーケンス番号であり,nはすべての駒の裏面を最小限に抑えるために必要な反転回数である.

Sample Input

2 10111111 00011111 10111111 11111111 11111111 11111111 11111111 11111111
10110001 00011011 10111111 11111111 11111011 11110001 11111111 11110001

Sample Output

Case 1: 1 Case 2: 4

#include<iostream>
#include<string>
using namespace std;
#define N 10
#define minn(x,y) ((x)<(y)?(x):(y))
char str[N];
int map[N][N],tmap[N][N],ans[N][N];

void Rev(int i,int j)
{
    tmap[i][j]=(tmap[i][j]+1)%2;
    if(i>0)
        tmap[i-1][j]=(tmap[i-1][j]+1)%2;
    if(i<8)
        tmap[i+1][j]=(tmap[i+1][j]+1)%2;
    if(j>0)
        tmap[i][j-1]=(tmap[i][j-1]+1)%2;
    if(j<8)
        tmap[i][j+1]=(tmap[i][j+1]+1)%2;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int times,i,j,k;
    scanf("%d",&times);
    for(k=1;k<=times;k++)
    {
        getchar();
        int min=256;
        for(i=0;i<8;i++)
        {
            scanf("%s",str);
            for(j=0;j<8;j++)
                map[i][j]=str[j]-'0';
        }
        for(int fl=0;fl<256;fl++)
        {
            int count=0;
            memset(ans,0,sizeof(ans));
            for(i=0;i<8;i++)
            {
                for(j=0;j<8;j++)
                    tmap[i][j]=map[i][j];
            }
            for(j=0;j<8;j++)
            {
                if(fl & (1<<j))
                {
                    Rev(0,j);
                    ans[0][j]=1;
                }
            }
            for(i=1;i<8;i++)
            {
                for(j=0;j<8;j++)
                if(!tmap[i-1][j])
                {
                    Rev(i,j);
                    ans[i][j]=1;
                }
            }
            for(i=0;i<8;i++)
                count+=tmap[7][i];
            if(count!=8)
                continue;
            count=0;
            for(i=0;i<8;i++)
            {
                for(j=0;j<8;j++)
                    count+=ans[i][j];
            }
            min=minn(min,count);
        }
        printf("Case %d: %d
",k,min);
    }
    return 0;
}