套路啊
棋盘黑白染色，S连黑，白连T，黑白间根据骑士的走法连边，求出最小割
最大独立集=点数-最小点覆盖；最小点覆盖=最大流=最小割
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# define ll long long
# define RG register
# define IL inline
# define Mem(a, b) memset(a, b, sizeof(a))
# define Max(a, b) (((a) > (b)) ? (a) : (b))
# define Min(a, b) (((a) < (b)) ? (a) : (b))
using namespace std;
IL int Get(){
RG char c = '!'; RG int x = 0, z;
for(; c > '9' || c < '0'; c = getchar()) z = (c == '-') ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
const int INF = 2147483647, MAXN = 40002, MAXM = 1000001;
int n, m, ft[MAXN], cnt, ans, map[201][201], Q[MAXM], level[MAXN], cur[MAXN];
int dx[] = {2, 1, -2, -1, 2, 1, -2, -1};
int dy[] = {1, 2, 1, 2, -1, -2, -1, -2};
struct Edge{
int to, nt, f;
} edge[MAXM];
IL void _Add(RG int u, RG int v, RG int f){
edge[cnt] = (Edge){v, ft[u], 1}; ft[u] = cnt++;
edge[cnt] = (Edge){u, ft[v], 0}; ft[v] = cnt++;
}
IL void Add(RG int x, RG int y){
RG int u = (x - 1) * n + y;
for(RG int i = 0; i < 8; i++){
RG int xx = x + dx[i], yy = y + dy[i];
if(xx <= 0 || xx > n || yy <= 0 || yy > n || map[xx][yy]) continue;
RG int v = (xx - 1) * n + yy;
_Add(u, v, 1);
}
}
IL int Dfs(RG int u, RG int T, RG int maxf){
if(u == T) return maxf;
RG int ret = 0;
for(RG int &e = cur[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(level[v] == level[u] + 1 && edge[e].f){
RG int f = Dfs(v, T, Min(maxf - ret, edge[e].f));
edge[e].f -= f; edge[e ^ 1].f += f;
ret += f;
if(ret == maxf) break;
}
}
return ret;
}
IL bool Bfs(RG int S, RG int T){
Mem(level, 0);
RG int head = 0, tail = 0;
Q[0] = S; level[S] = 1;
while(head <= tail){
RG int u = Q[head++];
if(u == T) return 1;
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(!level[v] && edge[e].f){
level[v] = level[u] + 1;
Q[++tail] = v;
}
}
}
return 0;
}
int main(){
Mem(ft, -1);
n = Get(); m = Get();
RG int S = 0, T = n * n + 1;
for(RG int i = 1; i <= m; i++)
map[Get()][Get()] = 1;
for(RG int i = 1; i <= n; i++)
for(RG int j = 1; j <= n; j++)
if(!map[i][j]){
if(~(i + j) & 1) _Add(S, (i - 1) * n + j, 1), Add(i, j);
else _Add((i - 1) * n + j, T, 1);
}
while(Bfs(S, T)){
for(RG int i = S; i <= T; i++)
cur[i] = ft[i];
ans += Dfs(S, T, INF);
}
printf("%d
", n * n - m - ans);
return 0;
}