C++ 代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 150,maxm = 1e6+10;
int a[maxn][maxn],cnt[maxn][maxn],cntx,n,t,tot,head[maxn*maxn],vis[maxn*maxn],link[maxn*maxn];
struct Edge{ int to,nxt; } e[maxm];
void add(int from,int to)
{
e[++tot].nxt = head[from],e[tot].to = to;
head[from] = tot;
}
bool find(int u)
{
for(int i = head[u];i;i=e[i].nxt)
{
int to = e[i].to;
if(!vis[to])
{
vis[to] = 1;
if(!link[to] || find(link[to])){
link[to] = u,link[u] = to;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&t);
int x,y;
while(t--)
{
scanf("%d%d",&x,&y);
a[x][y] = 1;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(!a[i][j]) cnt[i][j]=++cntx;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
if(!a[i][j])
{
if(j > 1 && !a[i][j-1]) add(cnt[i][j],cnt[i][j-1]);
if(j < n && !a[i][j+1]) add(cnt[i][j],cnt[i][j+1]);
if(i > 1 && !a[i-1][j]) add(cnt[i][j],cnt[i-1][j]);
if(i < n && !a[i+1][j]) add(cnt[i][j],cnt[i+1][j]);
}
}
int ans = 0;
for(int i = 1; i<= cntx; ++i)
{
if(!link[i])
{
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}
}
printf("%d\n",ans);
}