P10939 - 骑士放置 题解

1
#include <bits/stdc++.h>
2

3
#define N 210
4
using namespace std;
5

6
typedef pair<int, int> PII;
7

8
bool g[N][N];
9
PII match[N][N];
10
bool st[N][N];
11
int dx[8] = {-2, -1, 1, 2, -2, 1, -1, 2};
12
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
13
int n, m, k;
14

15
bool hungary(PII t) {
16
    for (int i = 0; i < 8; i++) {
17
        int nx = t.first + dx[i];
18
        int ny = t.second + dy[i];
19
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
20
        if (st[nx][ny] || g[nx][ny]) continue;
21
        st[nx][ny] = true;
22
        if (!match[nx][ny].first || hungary(match[nx][ny])) {
23
            match[nx][ny] = t;
24
            return true;
25
        }
26
    }
27
    return false;
28
}
29

30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    cout.tie(nullptr);
34

35
    cin >> n >> m >> k;
36
    for (int i = 1; i <= k; i++) {
37
        int a, b;
38
        cin >> a >> b;
39
        g[a][b] = true;
40
    }
41
    int res = 0;
42
    for (int i = 1; i <= n; i++) {
43
        for (int j = 1; j <= m; j++) {
44
            if ((i + j) % 2 || g[i][j]) continue;
45
            memset(st, false, sizeof st);
46
            if (hungary((PII) {i, j})) res++;
47
        }
48
    }
49
    cout << n * m - res - k << endl;
50
    return 0;
51
}