pku2226.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 50
#define psize 500
int path[psize][psize];
int vis[psize];
int match[psize];

char map[size][size];
int id1[size][size];
int id2[size][size];

int m, n, M, N;
int cnt;

int DFS(int p)
{
	int i, t;
	for (i = 0; i < N; i++)
	{
		if (!vis[i] && path[p][i])
		{
			vis[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}

void Solve()
{
	int i, j, cnt;
	for (i = 0; i < m; i++)
	{
		scanf("%s", map[i]);
	}
	memset(id1, -1, sizeof(id1));
	memset(id2, -1, sizeof(id2));
	M = 0;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (map[i][j] == '*')
			{
				if (j == 0 || map[i][j - 1] != '*')
					id1[i][j] = M++;
				else
					id1[i][j] = id1[i][j - 1];
			}
		}
	}
	N = 0;
	for (j = 0; j < n; j++)
	{
		for (i = 0; i < m; i++)
		{
			if (map[i][j] == '*')
			{
				if (i == 0 || map[i - 1][j] != '*')
					id2[i][j] = N++;
				else
					id2[i][j] = N - 1;
			}
		}
	}
	memset(path, 0, sizeof(path));
	memset(match, -1, sizeof(match));
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (map[i][j] == '*')
				path[id1[i][j]][id2[i][j]] = 1;
		}
	}
	for (i = 0, cnt = 0; i < M; i++)
	{
		memset(vis, 0, sizeof(vis));
		cnt += DFS(i);
	}
	printf("%d\n", cnt);
}

int main()
{
	while (EOF != scanf("%d %d", &m, &n))
	{
		Solve();
	}
	return 0;
}