题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4185

       题意是输入n*n的地图，然后问最多有多少个1*2或者2*1的'#'。

       思路就是用二分图，将相邻的'#'连一条边，然后在n*n的图内跑一个最大匹配数。难就难在如何去建图，我们把每个'#'的坐标记为一个数，然后对于两个相邻的'#'，直接用刚才所标记的数进行建边，坑点是因为是n*n的地图，如果有n*n个'#'的话，就需要开maxn*maxn个数组，还有就是vector初始化的时候也是n*n，这一点需要注意。

AC代码：

#include <bits/stdc++.h>
#define maxn 610
using namespace std;
vector<int> G[maxn];
int pre[maxn][maxn];
int mat[maxn * maxn];
bool vis[maxn * maxn];
string str[maxn];
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
int T,n,cnt;

void init(){
	cnt = 1;
	memset(mat,-1,sizeof(mat));
	memset(pre,0,sizeof(pre));
	for(int i=0;i<=n*n;i++){
		G[i].clear();
	}
}

bool dfs(int x){
	for(int i=0;i<G[x].size();i++){
		int v = G[x][i];
		if(vis[v] == false){
			vis[v] = true;
			if(mat[v] == -1 || dfs(mat[v])){
				mat[v] = x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int Case = 1;
	scanf("%d",&T);
	while(T--){
		init();
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			cin>>str[i];
			for(int j=0;j<n;j++)
				if(str[i][j] == '#') pre[i][j] = cnt ++;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(str[i][j] == '#'){
					for(int k=0;k<4;k++){
						int xx = i + dir[k][0];
						int yy = j + dir[k][1];
						if(xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
						if(str[xx][yy] == '#'){
							G[pre[xx][yy]].push_back(pre[i][j]);
							G[pre[i][j]].push_back(pre[xx][yy]);
						}
					}
				}
			}
		}
		int ans = 0;
		for(int i=1;i<=cnt;i++){
			memset(vis,false,sizeof(vis));
			if(dfs(i)) ans ++;
		}
		printf("Case %d: %d\n",Case ++, ans / 2);
	}
	return 0;
}