题目大意：
统计相邻（上下左右）的‘#’的对数。
解法：
与题目hdu1507 Uncle Tom's Inherited Land*类似，需要用奇偶建图。就是行+列为奇数的作为X集合，偶尔作为Y集合，都是‘#’就连边。最后求最大匹配。
数据有点大，直接建图会出错（我试过）。可以按照‘#’出现的顺序给顶点编号。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=36005,INF=0x3f3f3f3f;
int cx[N],cy[N],dx[N],dy[N];
bool bmask[N];
vector<int > bmap[N];
int nx,ny,dis,ans;
bool searchpath()
{
queue<int> q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=nx;i++)
{
if(cx[i]==-1){ q.push(i); dx[i]=0; }
while(!q.empty())
{
int u=q.front(); q.pop();
if(dx[u]>dis) break;
for(int i=0;i<bmap[u].size();i++)
{
int v=bmap[u][i];
if(dy[v]==-1)
{
dy[v]= dx[u] + 1;
if(cy[v]==-1) dis=dy[v];
else
{
dx[cy[v]]= dy[v]+1;
q.push(cy[v]);
}
}
}
}
}
return dis!=INF;
}
int findpath(int u)
{
for(int i=0;i<bmap[u].size();i++)
{
int v=bmap[u][i];
if(!bmask[v]&&dy[v]==dx[u]+1)
{
bmask[v]=1;
if(cy[v]!=-1&&dy[v]==dis) continue;
if(cy[v]==-1||findpath(cy[v]))
{
cy[v]=u; cx[u]=v;
return 1;
}
}
}
return 0;
}
void maxmatch()
{
ans=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(searchpath())
{
memset(bmask,0,sizeof(bmask));
for(int i=1;i<=nx;i++)
if(cx[i]==-1) ans+=findpath(i);
}
}
void init()
{
for(int i=0;i<=N;i++) bmap[i].clear();
}
char s[605][605];
int Map[605][605];
int main()
{
//freopen("test.txt","r",stdin);
int cas,n,i,j,k=1,a,b,t=1;
char ch;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
t=0;
for(i=1;i<=n;i++){
getchar();
for(j=1;j<=n;j++)
{
scanf("%c",&s[i][j]);
if(s[i][j]=='#') Map[i][j]=++t;
}
}
init();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(s[i][j]=='#'&&((i+j)%2))
{
a=Map[i][j];
if(i>1&&s[i-1][j]=='#'){
b=Map[i-1][j];
bmap[a].push_back(b);
}
if(i<n&&s[i+1][j]=='#'){
b=Map[i+1][j];
bmap[a].push_back(b);
}
if(j>1&&s[i][j-1]=='#'){
b=Map[i][j-1];
bmap[a].push_back(b);
}
if(j<n&&s[i][j+1]=='#'){
b=Map[i][j+1];
bmap[a].push_back(b);
}
}
}
}
nx=t;
maxmatch();
printf("Case %d: %d\n",k++,ans);
}
return 0;
}