题目链接：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代码：
代码语言：javascript复制#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: %dn",Case , ans / 2);
}
return 0;
}
