hungary

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=105;
int n, m;
PII match[N][N];
bool g[N][N], vis[N][N]; // hungary 标记数组
int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 定义方向向量

bool find(int x, int y){ // hungary find function
    for(int i=0; i<4; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(nx && nx<=n && ny && ny<=n && !g[nx][ny] && !vis[nx][ny]){
            vis[nx][ny]=true;
            PII t=match[nx][ny];
            if(t.fi==-1 || find(t.fi, t.se)){
                match[nx][ny]={x, y};
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin>>n>>m;
    while(m--){
        int x, y;
        cin>>x>>y;
        g[x][y]=true; // 读入障碍坐标
    }

    memset(match, -1, sizeof match);
    int ans=0;
    // 将图进行2-染色(0, 0)设置为黑色
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            if((i+j)&0x01 && !g[i][j]){ // 如果是白色格子并且可以无障碍
                memset(vis, 0x00, sizeof vis);
                if(find(i, j)) ans++;
            }
    cout<<ans<<endl;
    return 0;
}