题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104458880

一、内容

给定一个 N*M 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

输入格式

第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量。

接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。

输出格式

输出一个整数表示结果。

数据范围

1≤N,M≤100

输入样例：

2 3 0

输出样例：

4

二、思路

三、代码

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int dx[8] = {-2, -2, 2, 2, -1, -1, 1, 1};
int dy[8] = {-1, 1, -1, 1, -2, 2, -2, 2};
bool g[N][N], vis[N][N];
int n, m, t, x, y;
pair<int, int> mat[N][N];
bool dfs(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int fx = x + dx[i], fy = y + dy[i];
        if (fx <= 0 || fy <= 0 || fx > n || fy > m || g[fx][fy] || vis[fx][fy]) continue; vis[fx][fy] = true; 
        int px = mat[fx][fy].first, py = mat[fx][fy].second;
        if ((!px && !py) || dfs(px, py)) {
            mat[fx][fy] = make_pair(x, y); return true;
        }
    }
    return false;
}
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= t; i++) {
        scanf("%d%d", &x, &y); g[x][y] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] || ((i + j) & 1)) continue;
            memset(vis, false, sizeof(vis));
            if (dfs(i, j)) ans++;
        }
    }
    printf("%d\n", n * m - t - ans);
    return 0;
}