You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
76 lines
2.3 KiB
76 lines
2.3 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int N = 100 * 100 + 10, M = 8 * N; // 注意点的数量,每个点最多8个方向
|
|
|
|
// 链式前向星
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
void add(int a, int b, int c = 0) {
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
}
|
|
// 棋盘专用dx8
|
|
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
|
|
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
|
|
|
|
int n, m, k;
|
|
int g[110][110]; // 禁止放置的位置
|
|
|
|
// 匈牙利算法专用数组
|
|
int match[N], st[N];
|
|
int dfs(int u) {
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
int v = e[i];
|
|
if (!st[v]) {
|
|
st[v] = 1;
|
|
if (!match[v] || dfs(match[v])) {
|
|
match[v] = u;
|
|
return 1;
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("378.in", "r", stdin);
|
|
#endif
|
|
// 初始化链式前向星
|
|
memset(h, -1, sizeof h);
|
|
|
|
scanf("%d %d %d", &n, &m, &k);
|
|
|
|
// 不可以放置的位置记录
|
|
for (int i = 1; i <= k; i++) {
|
|
int x, y;
|
|
scanf("%d %d", &x, &y);
|
|
g[x][y] = 1;
|
|
}
|
|
|
|
// 使用链式前向星建图
|
|
vector<int> vec;
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 1; j <= m; j++) {
|
|
if ((i + j) % 2 && !g[i][j]) { // 横纵坐标和为奇数，并且，此位置没有被禁止
|
|
int id = (i - 1) * m + j;
|
|
vec.push_back(id);
|
|
for (int k = 0; k < 8; k++) { // 8个方向建边
|
|
int tx = i + dx[k], ty = j + dy[k];
|
|
int tid = (tx - 1) * m + ty;
|
|
if (tx < 1 || tx > n || ty < 1 || ty > m) continue; // 出界不要
|
|
if (g[tx][ty]) continue; // 被禁止不行
|
|
add(id, tid); // 建边,注意一下二维坐标与点号的映射关系。同时，由于正反都可以创建，这里就不用一次建两条
|
|
}
|
|
}
|
|
}
|
|
|
|
int res = 0;
|
|
for (auto id : vec) {
|
|
memset(st, 0, sizeof st);
|
|
if (dfs(id)) res++; // 开始跑匈牙利算法
|
|
}
|
|
|
|
// 最大独立集 n-无法放的点-最大匹配数
|
|
printf("%d\n", n * m - k - res);
|
|
return 0;
|
|
} |