骑士放置

AcWing-378-骑士放置

分析

见《进阶指南》第435页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 10010;
const int dx[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };
const int dy[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
struct edge {
    int to, next;
};
edge e[8 * M];
int idx, head[M];
int n, m, k;
int a[N][N];
bool mark[M];
int match[M];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
bool dfs (int cur) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (mark[to] == true) continue;
        mark[to] = true;
        if (match[to] == 0 || dfs(match[to]) == true) {
            match[to] = cur;
            return true;
        }
    }
    return false;
}
int index_of (int i, int j) {
    return (i - 1) * m + j;
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n >> m >> k;
    for (int i = 1, x, y; i <= k; ++ i) {
        cin >> x >> y;
        a[x][y] = -1;
    }
    
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            if (a[i][j] == -1) continue;
            for (int k = 0; k < 8; ++ k) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (a[nx][ny] == -1) continue;
                add_edge(index_of(i, j), index_of(nx, ny));
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            if (a[i][j] == -1 || (i + j) % 2 == 0) continue;
            memset(mark, 0, sizeof(mark));
            if (dfs(index_of(i, j)) == true) ++ cnt;
        }
    }
    cout << ((n * m - k) - cnt) << endl;
    return 0;
}