place the robots(二分匹配).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm> 
using namespace std; 

const int NMAX = 3100;
const int MMAX = 60;

int match[NMAX];
bool flag[NMAX];
int w, h, n;
char path[MMAX][MMAX];
vector< vector<int> > Bmap;
int nx, ny;

bool dfs(int pos) 
{ 
	int i;
	for(i=0; i < Bmap[pos].size() ;i++) { 
		int t = Bmap[pos][i];
		if(!flag[t]) { 
			flag[t] = true;
			int pre = match[t];
			match[t] = pos;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			match[t] = pre;
		}
	}
	return false;
}

int Max_Match() 
{
	int i, j;
	// matching，find augmented path and mark
	int max_match = 0;
	memset(match, -1, sizeof(match));
	for(i=0; i < nx ;i++) {
		memset(flag, false, sizeof(flag)); 
		if( dfs(i) ) {
			max_match ++;
		}
	}
	return max_match;
}

//横轴空地块，竖轴空地块
int x[MMAX][MMAX], y[MMAX][MMAX];

void make_graph()
{
	int i,j,k,pre;
	bool newf;

	nx = ny = 0;
	newf = false;
	for(i=0;i<h;i++) {
		gets(path[i]);
		pre = -1;
		for(j=0;j<w;j++) {
			switch(path[i][j]) {
			case 'o':
				if(newf) {
					nx ++;
				}
				x[i][j] = nx;
				pre = nx;
				newf = false;
				break;
			case '#':
				newf = true;
				pre = -1;
			default:
				x[i][j] = pre;
			}
		}
		newf = true;
	}
	pre = -1;
	newf = false;
	for(i=0;i<w;i++) {
		pre = -1;
		for(j=0;j<h;j++) {
			switch(path[j][i]) {
			case 'o':
				if(newf) {
					ny ++;
				}
				y[j][i] = ny;
				newf = false;
				pre = ny;
				break;
			case '#':
				newf = true;
				pre = -1;
			default:
				y[j][i] = pre;
			}
		}
		newf = true;
	}
	nx ++;
	ny ++;
	n = nx + ny;
	Bmap.clear();
	Bmap.resize(n+10);
	//一条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。
	for(i=0;i<h;i++) {
		for(j=0;j<w;j++) {
			if(path[i][j] == 'o') {
				Bmap[ x[i][j] ].push_back( nx+y[i][j] );
			}
		}
	}
}

int main() 
{  
	int i, j, t;
	scanf("%d", &t);
	for(i=1;i<=t;i++) {
		printf("Case :%d\n", i);
		scanf("%d %d", &h,&w);
		getchar();
		make_graph();
		printf("%d\n", Max_Match());
	}
	return 0; 
}