#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

bool xihuan[405][405];
int dui[405][405],dui1[405][405];

bool zhao(int x,int y,int lx,int ly)
{
	if(xihuan[x][y-1] && y>1 && y-1!=ly)
	{
		if(dui[x][y-1]==0)
		{
			dui[x][y]=x;
			dui1[x][y]=y-1;
			dui[x][y-1]=x;
			dui1[x][y-1]=y;
			return true;
		}
		if(zhao(dui[x][y-1],dui1[x][y-1],x,y-1)&&(dui[x][y-1]!=lx || dui1[x][y-1]!=ly))
		{
			dui[x][y]=x;
			dui1[x][y]=y-1;
			dui[x][y-1]=x;
			dui1[x][y-1]=y;
			return true;
		}
	}
	if(xihuan[x-1][y] && x>1 && x-1!=lx)
	{
		if(dui[x-1][y]==0)
		{
			dui[x][y]=x-1;
			dui1[x][y]=y;
			dui[x-1][y]=x;
			dui[x-1][y]=y;
			return true;
		}
		if(zhao(dui[x-1][y],dui1[x-1][y],x-1,y)&&(dui[x-1][y]!=lx || dui1[x-1][y]!=ly))
		{
			dui[x][y]=x-1;
			dui1[x][y]=y;
			dui[x-1][y]=x;
			dui1[x-1][y]=y;
			return true;
		}
	}
	return false;
}

int main()
{
	int T,n,m;char c;
	scanf("%d",&T);
	for(int p=1;p<=T;p++)
	{
		scanf("%d %d",&n,&m);
		memset(xihuan,false,sizeof(xihuan));
		for(int i=1;i<=n;i++)
		{
			scanf("\n");
			for(int j=1;j<=m;j++)
			{
				scanf("%c",&c);
				if(c=='*') xihuan[i][j]=true;
			}
		}
		int ans=0;
		memset(dui,0,sizeof(dui));
		memset(dui1,0,sizeof(dui1));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(xihuan[i][j])
				{
					//printf("%d %d\n",i,j);
					if(zhao(i,j,i,j)) ans++;
				}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(xihuan[i][j] && dui[i][j]==0) ans++;
		printf("%d\n",ans);
	}
}

• Re:第一题匈牙利二分图 (1739) guyindu 2016-01-06 13:35:58