二分图最大匹配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, k;
PII match[N][N];
bool g[N][N], vis[N][N];
// 日型跳跃方向
int dirs[8][2]={{-2, 1}, {-2, -1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

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

int main(){
    memset(g, 0x00, sizeof g);
    memset(match, 0x00, sizeof match);
    cin>>n>>m>>k;
    for(int i=0; i<k; ++i){
        int a, b;
        cin>>a>>b; // 读入障碍点
        g[a][b]=true;
    }

    int ans=0;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            if(g[i][j] || (i+j)&0x01) continue; // 从坐标和为偶数向奇数匹配
            memset(vis, 0x00, sizeof vis);
            if(find(i, j)) ++ans;
        }
    }
    cout<<n*m-k-ans<<endl;
    return 0;
}