hdu1045 行列缩点+二分图匹配

题意：目标是尽可能多地在城市中设置碉堡，这样就不会有两个碉堡相互摧毁。如果没有两个碉堡在地图的同一水平行或垂直列上，除非至少有一个墙将它们分开，否则碉堡的配置是合法的。在这个问题中，我们将考虑小方形城市（最多4x4），其中包含无法穿过子弹的墙壁。
下图显示了同一块板的五张图片。第一张图片是空白板，第二张和第三张图片显示合法配置，第四张和第五张图片显示非法配置。对于该板，合法配置中的最大块仓数为5; 第二张图片显示了一种方法，但还有其他几种方法。
您的任务是编写一个程序，在给定地图描述的情况下，计算可以在合法配置中放置在城市中的最大数量的阻止房屋。

分析：一开始看见这题我并不是很知道怎么写，不清楚怎么建图，看了题解才理解，这道题是一个求二分图最大匹配的题目，关键在于怎么建图。他由于你放了一个点，你就不能在同一行，同一列上在放一个点，就是去分别行列锁点建图。把同一列的不被阻碍的作为同一点，把同一行不被阻碍的作为同一点。然后建图就是建立行与列之间的联系。如图

你某一个点在这个列上占据了一定的格子数，然后就在那个占领格子数的位置的缩行点的那个点的值建立联系。举个例子，上图左边（1,1）（2,1）缩成一个点1；
然后在同样的位置行缩点那里（1,1）是缩成点1，（2,1）是缩成点3.所以就建立1与1,1与3的联系。按照这个步骤去做图在求最大匹配也就是答案了。为什么这样去求二分图匹配就是答案？因为你是建立了行与列之间的联系，就是你某个点选了后，已经无法再选另一个在这个点的范围点的另外的点如左边格子数（1，1）和（2,1）被缩成点1，你就不会去表示到（1,1）和（2,1）同时取的情况，这两个互斥点只会去选取一个(对于列)，然后对于行也是同理的。所以满足条件的个数也就是最大匹配数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<cmath>
#define ll long long
using namespace std;
const long long max_ = 1e3 + 7;
int tu[max_][max_];
char node[max_][max_];
int diany[max_][max_], numy = 0, numx = 0;
int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int n, m, e, vis[max_], match[max_];
int dfs(int now) {
	for (int i = 1; i <= numy; i++) {
		if (tu[now][i] && !vis[i]) {
			vis[i] = 1;
			if (match[i] == 0 || dfs(match[i])) {
				match[i] = now;
				return 1;
			}
		}
	}
	return 0;
}
void qing() {
	numy = 0, numx = 0;
	memset(tu ,0, sizeof(tu));
	memset(match, 0, sizeof(match));
	memset(vis, 0, sizeof(vis));
	memset(diany, 0, sizeof(diany));
	memset(node, '\0', sizeof(node));
}
int main() {
	
	while(cin>>n&&n!=0) {
		qing();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin>> node[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (node[i][j] != 'X') numy++;
				while (node[i][j]!='X' && j <= n)
				{
					diany[i][j] = numy;
					j++;
				}
			}
		}
		for (int j = 1; j <= n; j++) {
			for (int i = 1; i <= n; i++) {
				if (node[i][j] != 'X')numx++;
				while (node[i][j] != 'X'&& i <= n)
				{
					if (diany[i][j] != diany[i - 1][j]) {
						tu[numx][diany[i][j]] = 1;
					}
					i++;
				}
			}
		}
		int sum = 0;
		for (int i = 1; i <= numx; i++) {
			memset(vis, 0, sizeof(vis));
			sum += dfs(i);
		}
		cout << sum << endl;
		
	}
	
	return 0;
}