|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef pair<int, int> PII;
|
|
|
#define x first
|
|
|
#define y second
|
|
|
|
|
|
const int N = 110;
|
|
|
|
|
|
int n, m, k;
|
|
|
PII match[N][N];
|
|
|
int g[N][N], st[N][N];
|
|
|
|
|
|
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
|
|
|
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
|
|
|
|
|
|
int find(int x, int y) {
|
|
|
for (int i = 0; i < 8; i++) {
|
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
|
if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
|
|
|
if (g[tx][ty] || st[tx][ty]) continue;
|
|
|
|
|
|
// 男[x,y] 找到女[tx,ty]
|
|
|
st[tx][ty] = 1;
|
|
|
// t为女[tx,ty]现在匹配的对象
|
|
|
PII t = match[tx][ty];
|
|
|
// 如果女[tx,ty]没有匹配对象,或者,现配t可以去找其他妹子,那就把[tx,ty]给[x,y]
|
|
|
if (t.x == 0 || find(t.x, t.y)) {
|
|
|
match[tx][ty] = {x, y};
|
|
|
return 1;
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
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; // 不可以放置
|
|
|
}
|
|
|
|
|
|
int res = 0;
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= m; j++) {
|
|
|
//(i,j)位置不可以放 只看i+j是奇数的点（偶数的点是一样的）
|
|
|
if ((i + j) % 2 && !g[i][j]) {
|
|
|
memset(st, 0, sizeof st);
|
|
|
if (find(i, j)) res++; // 开始跑匈牙利算法
|
|
|
}
|
|
|
}
|
|
|
// 最大独立集 n-无法放的点-最大匹配数
|
|
|
printf("%d\n", n * m - k - res);
|
|
|
return 0;
|
|
|
} |
