飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24665

题意：就是说给你个矩阵，你把0变为1，使矩阵中各个点的上下左右相加为偶数（如果上下左右存在的话），求改变最少的0的数量

分析：如果枚举每个点的话肯定就TLE了，但是我们可以只枚举第一行就行。。。这样就可以推出下面所有的行，因为下面的行可以根据当前行的上左右推出来，复杂度为2^n*(n^2),可以接受~，啪啪啪，AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=20;
int T,n;
int ai[maxn][maxn];
int bi[maxn][maxn];
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d",&ai[i][j]);
        }
    }
}
int MIN;
void DFS(int depth,int sum)
{

    if(depth>n)
    {
        int now=sum;
        memset(bi,0,sizeof(bi));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                bi[i][j]=ai[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                int tm=bi[i-1][j]+bi[i][j-1]+bi[i][j+1];
                if(tm%2==0)
                {
                    if(bi[i+1][j]==1)return;
                    else continue;
                }
                else
                {
                    if(bi[i+1][j]==0&&i+1<=n)
                    {
                        bi[i+1][j]=1;
                        now++;
                    }
                    else if(bi[i+1][j]==1)continue;
                    else
                    {
                        return;
                    }
                }
            }
        }
        MIN=min(now,MIN);
        return;

    }
    DFS(depth+1,sum);
    if(ai[1][depth]==0)
    {
        ai[1][depth]=1;
        DFS(depth+1,sum+1);
        ai[1][depth]=0;
    }

}
void play(int Case)
{
    MIN=1000000000;
    DFS(1,0);
    if(MIN==1000000000)MIN=-1;
    printf("Case %d: %d\n",Case,MIN);
}
int Case;
int main()
{   Case=1;
    scanf("%d",&T);
    while(T--)
    {
        init();
        play(Case);
        Case++;
    }
    //cout << "Hello world!" << endl;
    return 0;
}