骑士共存问题

题目描述

在一个 $n \times n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。  对于给定的 $n \times n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

输入输出格式

输入格式

 

第一行有 $2$ 个正整数 $n$ 和 $m$ ，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 $2$ 个正整数，表示障碍的方格坐标。

输出格式

 

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

输入输出样例

输入样例 #1

3 2
1 1
3 3

输出样例 #1

5

说明

#### 数据规模与约定 对于全部的测试点，保证 $1 \leq n \leq 200$，$0 \leq m \lt n^2$。    

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 const int N = 300;
 8 #define PII pair <int, int>
 9 PII match[N][N];
10 int vis[N][N], now;
11 int g[N][N];
12 int  n , m;
13 
14 int dx[8] = {1 , 1, -1, -1, 2, 2 ,-2, -2 };
15 int dy[8] = {2, -2 ,2, -2 , 1 ,-1, 1, -1 };
16 
17 bool find(int x,int y)
18 {
19     for(int i = 0; i < 8; i++)
20     {
21         int a = x + dx[i], b = y + dy[i];
22         if(a < 1 || a > n || b < 1 || b > n) continue;
23         if(g[a][b]) continue;
24         if (vis[a][b] != now)
25         {
26             vis[a][b] = now;
27             PII t = match[a][b];
28             if(t.first == 0 || find(t.first, t.second))
29             {
30                 match[a][b] = make_pair(x, y);
31                 return 1;
32             }
33         }
34     }
35     return 0;
36 }
37 
38 int main()
39 {
40     //freopen("3355.in", "r", stdin);
41     scanf("%d %d",&n,&m);
42     for(int i = 1; i <= m; i++)
43     {
44         int a, b;
45         scanf("%d %d",&a,&b);
46         g[a][b] = 1;
47     }
48     int res = 0;
49     for(int i = 1; i <= n; i++)
50     {
51         for(int j = 1; j <= n; j++)
52         {
53             if(g[i][j] || (i + j) % 2 == 0) continue;
54             now++;
55             if(find(i, j)) res++;
56         }
57     }
58     printf("%d", n * n - m - res);
59     return 0;
60 }