题目链接

#include<bits/stdc++.h>
using namespace std;
vector<int>a[10001];
int ans;
int bj[10001],vis[10001];
bool bian[10001];
bool dfs(int p,int cnt){
//	printf("%d %d\n",p,cnt);
	for(auto it:a[p]){
		if(bj[it]!=cnt){
			bj[it]=cnt;
			if(!vis[it]||dfs(vis[it],cnt)){
				vis[it]=p;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		bian[(x-1)*n+y]=1;
	}
	for(int i=1;i<=n*n;i++){
		if(bian[i]){
			continue;
		}
		if(!bian[i+1]&&i+1<=n*n&&i%n!=0){
			a[i].push_back(i+1);
//			printf("%d %d\n",i,i+1);
		}
		if(!bian[i-1]&&i-1>=1&&i%n!=1){
			a[i].push_back(i-1);
//			printf("%d %d\n",i,i-1);
		}
		if(!bian[i+n]&&i+n<=n*n){
			a[i].push_back(i+n);
//			printf("%d %d\n",i,i+n);
		}
		if(!bian[i-n]&&i-n>=1){
			a[i].push_back(i-n);
//			printf("%d %d\n",i,i-n);
		}
	}
	for(int i=1;i<=n*n;i+=2){
		if(dfs(i,i)) ans++;
	}
	printf("%d",ans);
	return 0;
}