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

一、内容

给定一个N行N列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数N和t，其中t为禁止放置的格子的数量。

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

输出格式

输出一个整数，表示结果。

数据范围

1≤N≤100

输出样例：

8 0

输出样例：

32

二、思路

三、代码

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105, M = 4e4 + 5;
struct E {int v, next;} e[M];
int n, t, x, y, len, h[N * N], mat[N * N];
bool vis[N * N], g[N][N];
void add(int u, int  v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;} 
bool dfs(int u) {
    for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (vis[v]) continue;
        vis[v] = true;
        if (!mat[v] || dfs(mat[v])) {
            mat[v] = u; return true;
        }
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &t);
    while (t--) {
        scanf("%d%d", &x, &y); g[x][y] = true; 
    }
    //建立二分图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++) {
            if (g[i][j] || g[i][j + 1]) continue;
            int u = (i - 1) * n + j, v = u + 1;
            add(u, v); add(v, u); 
        }
    } 
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] || g[i + 1][j]) continue;
            int u = (i - 1) * n + j, v = i * n + j;
            add(u, v), add(v, u);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] || ((i + j) % 2 == 1)) continue; 
            int u = (i - 1) * n + j;
            memset(vis, false, sizeof(vis));
            if (dfs(u)) ans++;
        }
    } 
    printf("%d\n", ans);
    return 0;
}