棋盘覆盖

// 372. 棋盘覆盖.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/374/

给定一个 N行 N 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式
第一行包含两个整数 N和 t
，其中 t为禁止放置的格子的数量。

接下来 t行每行包含两个整数 x 和 y
，表示位于第 x行第 y 列的格子禁止放置，行列数从 1开始。

输出格式
输出一个整数，表示结果。

数据范围
1≤N≤100
,
0≤t≤100
输入样例：
8 0
输出样例：
32
*/


#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

unordered_set<int> ss;
int addx[] = { 0,1,0,-1 };
int addy[] = { 1,0,-1,0 };
const int N = 1000100;
const int M = 40010;
int h[N], e[M], ne[M], idx;
int n, m;
bool st[N];
int match[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int x) {
	for (int i = h[x]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) {
			st[j] = true;
			if (match[j] == 0 || find(match[j])) {
				match[j] = x;
				return true;
			}
		}
	}

	return false;
}

int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		ss.insert(a * 1000 + b);
	}

	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= n; y++) {
			int curr = x * 1000 + y;
			if ((x + y) % 2 != 0) continue;
			if (ss.count(x * 1000 + y) != 0) continue;
			for (int i = 0; i < 4; i++) {
				int newx = x + addx[i];
				int newy = y + addy[i];
				if (newx<1 || newx>n || newy<1 || newy>n) continue;
				if (ss.count(newx * 1000 + newy) != 0) continue;
				add(x * 1000 + y, newx * 1000 + newy);
			}
		}
	}

	int res = 0;
	//最大匹配
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= n; y++) {
			int curr = x * 1000 + y;
			if ((x + y) % 2 != 0) continue;
			if (ss.count(x * 1000 + y) != 0) continue;
			memset(st, 0, sizeof st);
			if (find(curr)) res++;
		}
	}

	cout << res*2 << endl;
	return 0;
}

注意答案 有的问覆盖的格子 有的问覆盖用的骨牌。