2998888_ac_15ms_708k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int map[401][401];
int link[401], b[401];
char str[41][11];
int d[41][11];
int num;

int dfs(int v)
{
	int i;
		
	for (i = 1; i <= num; i++)
	{
		if (map[v][i]==1&&b[i]==0)
		{
			b[i] = 1;
			if (link[i]==0||dfs(link[i])==1)
			{
				link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

void OLE()
{
	while(1)
	{
		puts("I LOVE U Shengqi");
	}
}

int main()
{
	int i, j, t;
	int m, n, cas, ans;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&m,&n);
		num = ans = 0;
		for(i = 0; i < m; i++)
		{
			scanf("%s",str[i]);
		}
		memset(map,0,sizeof(map));
		for(i = 0; i < m; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(str[i][j]=='*')
				{
					d[i][j] = ++num;
				}
			}
		}
		for (i = 0; i < m; i++)
		{
			for (j = 0; j < n; j++)
			{
				if(str[i][j]=='*')
				{
					t = d[i][j];
					if (i-1>=0&&str[i-1][j]=='*') map[t][d[i-1][j]]=1;
			        if (j-1>=0&&str[i][j-1]=='*') map[t][d[i][j-1]]=1;
			        if (i+1<m&&str[i+1][j]=='*') map[t][d[i+1][j]]=1;
			        if (j+1<n&&str[i][j+1]=='*') map[t][d[i][j+1]]=1;
				}

			}
		}
		memset(link,0,sizeof(link));
		for(i = 1; i <= num; i++)
		{
			memset(b,0,sizeof(b));
			ans += dfs(i);
		}
		if(ans%2==1)
		{
			OLE();
		}
		printf("%d\n",ans/2+num-ans);
	}
	return 0;
}