Hdu 5093 Battle Ship

每个海面要么放要么不放，因此可以用二分图匹配， 考虑把同一行内的能互相看到的点放到一个行块里，同一列内能看到的点放到一个列块里，然后每一个行块都可以和该行块里所有海面的列块连边，选了这个行块，就必须选且只选择一个该行块里的一个海面对应的列块。

#include <iostream>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 10100

using namespace std;

struct edg {

	int to, nex;

}e[N];

char ma[101][101];

int n, m, T, n1, n2, cnt, cntx, cnty;

int flag[N], lin[N], x[101][101], y[101][101], vis[N];

void add(int f, int t)

{

	e[++cnt].to = t;

	e[cnt].nex = lin[f];

	lin[f] = cnt;

}

bool dfs(int now)

{

	for (int i = lin[now]; i; i = e[i].nex)

	{

		int to = e[i].to;

		if (vis[to]) continue;

		vis[to] = 1;

		if (flag[to] == -1 || dfs(flag[to]))

		{

			flag[to] = now;

			return 1;

		}

	}

	return 0;

}

void clea()

{

	memset(flag, -1, sizeof(flag));

	memset(e, 0, sizeof(e));

	memset(lin, 0, sizeof(lin));

	memset(vis, 0, sizeof(vis));

	cnt = 0;

	cntx = cnty = 1;

}

int main()

{

 	scanf("%d", &T);

 	while (T--)

 	{

	 	clea();

	 	scanf("%d%d", &n, &m);

	 	char ca  = getchar();;

	 	for (int i = 1; i <= n; i++, ca = getchar())

	 		for (int j = 1; j <= m; j++)

	 			scanf("%c", &ma[i][j]);

	 	for (int i = 1; i <= n; i++, cntx++)

	 		for (int j = 1; j <= m; j++)

	 		{

	 			if (ma[i][j] == '*')//把属于同一行的数并到一起

	 				x[i][j] = cntx;

	 			if (ma[i][j] == '#')

	 				++cntx;

	 		}

	 	for (int i = 1; i <= m; i++, cnty++)

	 		for (int j = 1; j <= n; j++)

	 		{

	 			if (ma[j][i] == '*')

	 				y[j][i] = cnty;

	 			if (ma[j][i] == '#')

	 				++cnty;

	 		}

	 	for (int i = 1; i <= n; i++)

	 		for (int j = 1; j <= m; j++)

	 			if (ma[i][j] == '*')

	 				add(x[i][j], y[i][j]);

	 	n1 = cntx, n2 = cnty;

	 	int ans = 0;

	 	for (int i = 1; i <= n1; i++)

	 	{

	 		memset(vis, 0, sizeof(vis));

	 		if (dfs(i))

	 			ans++;

	 	}

	 	for (int i = 1; i <= n2; i++)

			if (flag[i]!=-1)

				printf("%d %d\n", flag[i], i);

	 	printf("%d\n", ans);

	}

	return 0;

}//

/*

1

4 4

*ooo

o###

**#*

ooo*

*/