F 棋盘覆盖
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 105 , M = N * N * 4 , ID = N * N + N;
int n,m;
int head[ID],ver[M],nxt[M],tot;
bool ban[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int match[ID];
bool v[ID];
void add(int x,int y) {
ver[++tot] = y , nxt[tot] = head[x] , head[x] = tot;
}
int get(int x,int y) {
return x * N + y;
}
bool dfs(int x) {
for(int i = head[x] ; i ; i = nxt[i]) {
int y = ver[i];
if(v[y]) continue;
v[y] = true;
if (!match[y] || dfs(match[y])) {
match[y] = x;
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
cin >> n >> m;
while (m--) {
int x,y;
cin >> x >> y;
ban[x][y] = true;
}
for(int x1 = 1 ; x1 <= n ; ++x1)
for(int y1 = 1 ; y1 <= n; ++y1) {
if(ban[x1][y1] || ( (x1 + y1) & 1) ) continue;
for(int k = 0 ; k < 4 ; ++k) {
int x2 = x1 + dx[k] , y2 = y1 + dy[k];
if(x2 < 1 || x2 > n || y2 < 1 || y2 > n || ban[x2][y2]) continue;
add(get(x1 , y1) , get(x2 , y2));
}
}
int ans = 0;
for(int x = 1 ; x <= n ; ++x)
for(int y = 1 ; y <= n ; ++y){
if(ban[x][y] || ( (x + y) & 1) ) continue;
memset(v , 0 , sizeof v);
if(dfs(get(x , y))) ++ans;
}
cout << ans << '\n';
return 0;
}