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

思路：

1. 男女配对问题，有障碍直接越过
2. 奇数格表示男生，偶数格表示女生

可参考： 二分图的最大匹配

#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;
bool g[N][N],st[N][N];
PII match[N][N];

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

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

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

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

        //表示该格子已填
        st[a][b]=true;

        PII t=match[a][b];

        //该女生没有对象或她的男朋友有备胎
        if(t.x==0||find(t.x,t.y))
        {
            match[a][b]={x,y};
            return true;
        }
    }

    return false;
}

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

    while(m--)
    {
        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<=n;j++)
            if((i+j)%2&&!g[i][j])
            {
                memset(st,0,sizeof st);

                //该男生可以找到女朋友
                if(find(i,j)) res++;
            }

    cout<<res<<endl;

    return 0;
}