莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 此题本质是最大独立集问题，可转换为最大匹配数问题
2. 最大独立集 = 总点数 - 最小点覆盖 = 总点数 - 最大匹配数
3. 答案 = 总点数 - 障碍数 - 最大匹配数

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int n,m,k;
bool g[N][N],st[N][N];
PII match[N][N];

int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};

bool find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];

        //超出边界
        if(a<=0||a>n||b<=0||b>m) continue;

        //有障碍或已有棋子
        if(g[a][b]||st[a][b]) continue;

        st[a][b]=true;

        PII t=match[a][b];
        if(!t.x||find(t.x,t.y))
        {
            match[a][b]={x,y};
            return true;
        }
    }

    return false;
}

int main()
{
    cin>>n>>m>>k;

    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=true;
    }

    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((i+j)%2&&!g[i][j])
            {
                memset(st,0,sizeof st);
                if(find(i,j)) res++;
            }

    //最大独立集 = 总点数 - 最小点覆盖 = 总点数 - 最大匹配数
    cout<<n*m-k-res<<endl;

    return 0;
}