C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=100+10,INF=1e9;
map<pii, pii> match;
map<pii, bool> vis, ban;
map<pii, vector<pii> > p;
int n, m, dx[]={1,-1,0,0},dy[]={0,0,1,-1};
bool find(pii now)
{
for (int i = 0;i<p[now].size();i++)
{
pii j = p[now][i];
if(!vis[j])
{
vis[j] = 1;
if(match[j].first==0&&match[j].second==0||find(match[j]))
{
match[j] = now;
return true;
}
}
}
return false;
}
bool check(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= n;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m;i++)
{
int x, y;
cin >> x >> y;
ban[{x, y}] = 1;
}
for (int i = 1; i <= n;i++)
{
for (int j = 1 + ((i&1)?0:1); j <= n;j+=2)
{
if(ban[{i,j}])
continue;
for (int k = 0; k < 4;k++)
{
int x = dx[k] + i;
int y = dy[k] + j;
if(check(x,y)&&!ban[{x,y}])
{
p[{i, j}].push_back({x, y});
}
}
}
}
int ans = 0;
for(auto [a,b]:p)
{
vis.clear();
if(find(a))
ans++;
}
cout << ans;
return 0;
}