「ZOJ 1654」Place the Robots

Description

有一个 (N imes M) 的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

Hint

(1le N, Mle 50)

Solution

我们将 每一行、每一列被 墙 隔开，并且包含 空地 的 连续区域 称作“块”。

假如地图是这样子的：

注：图源自 XJ 课件，下同。

那么两种分割块的方式为：

图中数字为块的编号。显然一个块中最多只能放一个机器人。

如果我们将块视作点，如果横块于竖块相交于一个 空地，那么将其连边。

最后我们可以得到这么一张图：

上面是横块，下面是竖块。容易发现最终构成的是一张二分图。

由于空地对于的是边，所以 放置机器人就相当于选择边 。而块对应点，一个块只能放一个机器人，因此 一个点相邻的最多只允许一条边被选择 。

于是，二分图最大匹配。匈牙利算法即可，复杂度 (O(N imes M))。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : ZOJ 1654 Place the Robots
 */
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
const int N = 55;
char str[N][N];
int n, m;

int tag[2][N][N];
int cnt[2];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int dt[2][2] = {{0, 1}, {2, 3}};
void fill(int t, int x, int y, int c) {
	tag[t][x][y] = c;
	for (register int i = 0; i < 2; i++) {
		x += dx[dt[t][i]], y += dy[dt[t][i]];
		if (x < 1 || x > n || y < 1 || y > m) continue;
		if (tag[t][x][y] || str[x][y] == '#') continue;
		fill(t, x, y, c);
		x -= dx[dt[t][i]], y -= dy[dt[t][i]];
	}
}

vector<int> G[N * N];
inline void connect(int x, int y) {
	G[x].push_back(y);
}

int match[N * N], vis[N * N];
bool Dfs(int x, int t) {
	if (vis[x] == t) return false;
	vis[x] = t;
	for (vector<int>::iterator y = G[x].begin(); y != G[x].end(); y++)
		if (!match[*y] || Dfs(match[*y], t))
			return match[*y] = x, true;
	return false;
}

int solve() {
	memset(tag, 0, sizeof tag);
	memset(cnt, 0, sizeof cnt);
	for (register int t = 0; t < 2; t++)
		for (register int i = 1; i <= n; i++)
			for (register int j = 1; j <= m; j++)
				if (str[i][j] == 'o')
					if (!tag[t][i][j])
						fill(t, i, j, ++cnt[t]);
	
	for (register int i = 1; i <= cnt[0]; i++)
		G[i].clear();
	for (register int i = 1; i <= n; i++)
		for (register int j = 1; j <= m; j++)
			if (str[i][j] == 'o')
				connect(tag[0][i][j], tag[1][i][j]);
	
	memset(vis, 0, sizeof vis);
	memset(match, 0, sizeof match);
	int total = 0;
	for (register int i = 1; i <= cnt[0]; i++)
		total += int(Dfs(i, i));
	return total;
}

signed main() {
	int T; scanf("%d", &T);
	for (register int i = 1; i <= T; i++) {
		printf("Case :%d
", i);
		scanf("%d%d", &n, &m);
		for (register int i = 1; i <= n; i++)
			scanf("%s", str[i] + 1);
		printf("%d
", solve());
	}
}