POJ 3020 Antenna Placement

题目链接

题意：给定一个地图，‘*‘的地方要被覆盖上，每次可以用1 x 2的矩形去覆盖，问最少用几个能覆盖

思路：二分图匹配求最大独立集，相邻*之间连边，然后求最大独立集即可
看这数据范围，用轮廓线dp应该也能搞

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 45;
const int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

int t, h, w, cnt, to[N][N];
char str[N][N];
vector<int> g[N * N];

int left[N * N], vis[N * N];

bool dfs(int u) {
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (left[v] == -1 || dfs(left[v])) {
			left[v] = u;
			return true;
		}
	}
	return false;
}

int hungary() {
	int ans = 0;
	memset(left, -1, sizeof(left));
	for (int i = 0; i < cnt; i++) {
		memset(vis, 0, sizeof(vis));
		if (dfs(i)) ans++;
	}
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		cnt = 0;
		scanf("%d%d", &h, &w);
		for (int i = 0; i < h; i++) {
			scanf("%s", str[i]);
			for (int j = 0; j < w; j++) {
				if (str[i][j] == '*') {
					g[cnt].clear();
					to[i][j] = cnt++;
				}
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (str[i][j] == 'o') continue;
				for (int k = 0; k < 4; k++) {
					int x = i + d[k][0];
					int y = j + d[k][1];
					if (x < 0 || x >= h || y < 0 || y >= w || str[x][y] == 'o') continue;
					g[to[i][j]].push_back(to[x][y]);
				}
			}
		}
		printf("%d\n", cnt - hungary() / 2);
	}
	return 0;
}

POJ 3020 Antenna Placement（二分图匹配）