2349.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2349 on 2006-09-10 at 00:26:48 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int R = 64, C = 64, N = R*C;

vector<int> g[N];
int n, match[N], check[N];

int bitMatch();
bool dfs(int, int);

int main()
{
	char map[R][C];
	int r, c, rn[R][C], cn[R][C];
	
	while(scanf("%d %d\n", &r, &c) != EOF) {
		for(int i = 0; i < r; i++) gets(map[i]);
		int rx = 0, cx = 0;
		for(int i = 0; i < r; i++)
			for(int j = 0, prvs = 0; j < c; j++)
				if(map[i][j] == '.') prvs = 0;
				else {
					if(!prvs) rx++;
					prvs = 1; rn[i][j] = rx-1;
				}
		for(int i = 0; i < c; i++)
			for(int j = 0, prvs = 0; j < r; j++)
				if(map[j][i] == '.') prvs = 0;
				else {
					if(!prvs) cx++;
					prvs = 1; cn[j][i] = cx-1;
				}
		n = rx;
		for(int i = 0; i < n; i++) g[i].clear();
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				if(map[i][j] == '*') g[rn[i][j]].push_back(cn[i][j]);
		printf("%d\n", bitMatch());
	}
	
	return 0;
}

int bitMatch()
{
	int mth = 0;
	memset(match, -1, sizeof(match)); memset(check, -1, sizeof(check));
	for(int i = 0; i < n; i++)
		if(dfs(i, i)) mth++;
	return mth;
}
bool dfs(int p, int k)
{
	for(int i = g[p].size()-1; i >= 0; i--) {
		int no = g[p][i];
		if(check[no] == k) continue;
		check[no] = k;
		int t = match[no];
		match[no] = p;
		if(t == -1 || dfs(t, k)) return true;
		match[no] = t;
	}
	return false;
}