• 这个概念针对任意的无向图都是成立的。是指我们从图中选出最多的点集，使得选出的点之间都没有边。

• 另外还有一个与最大独立集相对的概念最大团，是指我们从图中选出最多的点集，使得选出的点之间都有边。

• 原图的最大独立集就是补图的最大团，原图的最大团就是补图的最大独立集。我们只需要掌握其中一个，另一个就自然掌握了。（所谓补图是指边互补，你有的边我没有，我有的边你没有）。

• 在二分图中，最大独立集t == 总点数n - 最大匹配数m。（这里的n是指两个集合中 点个数之和）证明如下：

• 最大独立集$\iff$去掉最少的点，将所有边都破坏掉，剩余的点就是最大独立集$\iff$找最小点覆盖$\iff$找最大匹配。

• 另外提一点，最大独立集问题在一般的图上是一个NPC问题，只有在二分图上才能使用匈牙利算法。

分析

• 将格子看成图中的点，如果两个马是可以相互攻击到的，则在这两个格子之间连一条边。则剩下的问题就变成了：我们可以最多可以选择多少点，使得这些点之间没有边。即最大独立集问题。

• 下面验证建立的图是二分图。如下图，可以看到马向八个方向跳的格子都是和其所在的格子沿着是不同的（这是因为偏移量一定是一个计数，一个偶数）：

• 根据分析，因此最终的结果为$n \times m - T -$最大匹配数量。

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m, k;
bool g[N][N];  // 代表是否有障碍物
PII match[N][N];
bool st[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y) {

    for (int i = 0; i < 8; i++) {

        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (g[a][b] || st[a][b]) continue;

        st[a][b] = true;

        PII t = match[a][b];
        if (t.x == 0 || find(t.x, t.y)) {
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}

int main() {

    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (g[i][j] || (i + j) % 2) continue;
            memset(st, 0, sizeof st);
            if (find(i, j)) res++;
        }

    cout << n * m - k - res << endl;

    return 0;
}