【棋盘覆盖——匈牙利算法】

题目

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], st[N][N];
PII match[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, t;
bool find(PII u)
{for(int i = 0; i < 4; i++){int x = u.x + dx[i], y = u.y + dy[i]; //遍历心仪女生if(x < 1 || y < 1 || x > n || y > n || g[x][y] || st[x][y]) continue;st[x][y] = 1; //指这次处理之后归宿确定（不可再次考虑）if(match[x][y].x == -1 || find(match[x][y])) //名花无主或者皆大欢喜{match[x][y] = u; //匹配return true; //报喜}}return false;
}
int main()
{cin >> n >> t;for(int i = 1; i <= t; i++){int a, b;cin >> a >> b;g[a][b] = 1;}memset(match, -1, sizeof match);int ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if((i + j) % 2 || g[i][j]) continue;memset(st, 0, sizeof st);if(find({i, j})) ans++;}}cout << ans;
}