#include 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 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; }