/
i+j为偶数和i+j为奇数的点的两个集合构成二分图的
两个点集，和为偶数的边的四周全是和为奇数的点，
满足二分图的性质，题目说 `` 人话，求以和为偶数和奇数的
点构成的二分图的最大匹配
/

`#include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] PII;

const int N=110;

int n,m;
int g[N][N];//为1代表i j的位置有障碍
PII ret[N][N];//表示i j对应的匹配点，是一个二维坐标
bool st[N][N];//表示i j有没有被访问过

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

bool find(PII t)
{
//对所有的临边进行遍历
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];

    if(!a||a>n||!b||b>n||g[a][b]||st[a][b]) continue;

    st[a][b]=true;

    if(ret[a][b].first==0||find(ret[a][b]))
    {
        ret[a][b]=t;
        return true;
    }
}

return false;

}

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

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

int res=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        //把和为奇数的点当成男生，过滤女生
        if((i+j)%2==0||g[i][j]==1) continue;
        //每次便利前，把所有的女生初始化为没有访问过
        memset(st,false,sizeof st);

        //如果i j可以找到女朋友  
        if(find({i,j})) res++;
    }

printf("%d\n",res);

return 0;

}`