在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。

对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。

输入描述
Input Description

第一行有2 个正整数n 和m (1<=n<=200, 0<=m<n^2)，
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。

输出描述
Output Description

将计算出的共存骑士数输出

样例输入
Sample Input

3 2

1 1

3 3

样例输出
Sample Output

5

数据范围及提示
Data Size & Hint

详见试题

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 inline void read(int &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '') c = ch, ch = getchar();

     while(ch <= '' && ch >= '') x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 const int MAXN =  + ;

 const int dx[] = {,-,,-,,-,,-};

 const int dy[] = {,-,,-,-,,-,};

 int gg[MAXN][MAXN], b[MAXN][MAXN], n, m, lk[],bb[];

 struct Edge

 {

     int u,v,next;

     Edge(int _u, int _v, int _next){u = _u;v = _v;next = _next;}

     Edge(){}

 }edge[];

 int head[];

 int dfs(int u)

 {

     for(int pos = head[u];pos;pos = edge[pos].next)

     {

         int v = edge[pos].v;

         if(bb[v])continue;

         bb[v] = ;

         if(lk[v] == - || dfs(lk[v]))

         {

             lk[v] = u;

             return ;

         }

     }

     return ;

 }

 int xiongyali(int white)

 {

     int ans = ;

     memset(lk, -, sizeof(lk));

     for(register int i = ;i <= white;++i)

     {

         memset(bb, , sizeof(bb));

         ans += dfs(i);

     }

     return ans;

 }

 int main()

 {

     read(n), read(m);

     register int black, white, i;

     for(i = ;i <= m;++ i)

     {

         read(black), read(white);

         b[black][white] = ;

     }

     //X集合：1 白色  Y集合：0 黑色

     black = white = ;

     for(i = ;i <= n;++ i)

         for(int j = ;j <= n;++ j)

             if(!b[i][j])

                 if((i + j)&) gg[i][j] = ++ black;

                 else gg[i][j] = ++ white;

     register int xx, yy, cnt = ;

     for(i = ;i <= n;++ i)

         for(int j = ;j <= n;++ j)

             if(!((i + j)&) && !b[i][j])

                 for(int k = ;k < ;++ k)

                 {

                     xx = i + dx[k], yy = j + dy[k];

                     if(xx <=  || yy <=  || xx > n || yy > n || b[xx][yy])continue;

                     yy = gg[xx][yy], xx = gg[i][j];

                     edge[++cnt] = Edge(xx,yy,head[xx]);

                     head[xx] = cnt;

                 }

     printf("%d", white + black - xiongyali(white));

     return ;

 }