学步园

    这是一道比较经典的二分匹配，将格子按黑白标记后，再将含'*'的格子按黑白分成两组，建边。最后的结果就是总的'*'的个数-匹配数。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>map[400];//按奇偶性建二分图 
int t,n,m;
int match[400],fy[400],ln,rn; 
int map1[41][11];//原始图 
int dirt[4][2]={0,1,0,-1,1,0,-1,0};

int path(int u)
{
	for(int i=0,j;i<map[u].size();i++)
	{
		j=map[u][i];
		if(!fy[j])
		{
			fy[j]=1;
			if(match[j]==-1||path(match[j]))
			{
				match[j]=u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int i,j,x,y,ans;
	char tmp;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		ln=rn=0;
		for(i=1;i<=n;i++)
		{
			getchar();
			for(j=1;j<=m;j++)
			{
				scanf("%c",&tmp);
				if(tmp=='*')
				{
					if((i+j)&1)//奇点 
						map1[i][j]=++ln;
					else//偶点 
						map1[i][j]=++rn;
				}
				else
					map1[i][j]=0;
			}
		}
		for(i=1;i<=ln;i++)
			map[i].clear();
		for(i=1;i<=rn;i++)
			match[i]=-1;
			
		//建二分图 
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(!map1[i][j]||!((i+j)&1))
					continue;
				for(int k=0;k<4;k++)
				{
					x=i+dirt[k][0];
					y=j+dirt[k][1];
					if(x<=0||x>n||y<=0||y>m||!map1[x][y])
						continue;
					map[map1[i][j]].push_back(map1[x][y]);
				}
			}
			
		//求最大匹配 
		ans=0;
		for(i=1;i<=ln;i++)
		{
			for(j=1;j<=rn;j++)
				fy[j]=0;
			if(path(i))
					ans++;
		}
		printf("%d\n",ln+rn-ans);
	}
	return 0;
}