1086.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1086 on 2006-01-09 at 14:46:22 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 8;
const int L_MAX = 4;

bool inter[MAX][MAX], check[MAX];
int match[MAX], m;

bool DFS(int);

int main()
{
	char board[L_MAX][L_MAX+1];
	int h[L_MAX][L_MAX], v[L_MAX][L_MAX];
	int n, i, j;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		int hn = -1, vn = -1;
		memset(inter, false, sizeof(inter)); getchar();
		for(i = 0; i < n; i++) gets(board[i]);
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++) {
				if(board[j][i] == 'X') v[j][i] = -1;
				else if(j == 0 || board[j-1][i] == 'X') v[j][i] = ++vn;
				else v[j][i] = vn;
				if(board[i][j] == 'X') h[i][j] = -1;
				else if(j == 0 || board[i][j-1] == 'X') h[i][j] = ++hn;
				else h[i][j] = hn;
			}
		}
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++) {
				if(board[i][j] != 'X') inter[h[i][j]][v[i][j]] = true;
			}
		}
		memset(match, -1, sizeof(match));
		int pos = 0; m = max(hn, vn) + 1;
		for(i = 0; i < m; i++) {
			memset(check, false, sizeof(check));
			if(DFS(i)) pos++;
		}
		printf("%d\n", pos);
	}
	
	return 0;
}

bool DFS(int p)
{
	int i;
	for(i = 0; i < m; i++) {
		if(!check[i] && inter[i][p]) {
			check[i] = true;
			int t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t)) return true;
			else match[i] = t;
		}
	}
	return false;
}