二分图——骑士放置（最大独立集）

骑士放置

在一个尺寸为N*M的棋盘上，存在若干个不允许放置棋子的格子。问题要求确定在该棋盘上最多可以放置多少个骑士，且这些骑士之间不能相互攻击。此处所指的骑士为国际象棋中的骑士，其攻击方式类似于中国象棋中的“马”，按照“日”字形移动方式进行攻击，但不遵循中国象棋中“别马腿”的规则。

输入格式方面，第一行包括三个整数N、M和T，其中T代表被禁止放置棋子的格子数量。随后的T行中，每行包含两个整数x和y，表示位于第x行第y列的格子被禁止放置棋子，行列编号均从1开始。

输出格式要求为一个整数，用于表示最终结果。

数据范围限定为：1≤N,M≤100。

输入样例如下：
2 3 0

对应的输出样例为：
4

题解：

通过采用奇偶染色法进行分析，将奇数位置标记为黑色（可在草稿纸上进行标记），可以发现当当前格子的横纵坐标均为偶数时，其被攻击的位置必定处于黑色区域。因此，该图结构符合二分图的特征。（此结论未经过严格证明，仅基于解题经验得出）。接下来，在所有能够相互攻击的位置之间建立连接边。题目要求棋子之间不能互相攻击，并且需要尽可能多地摆放棋子。由此可知，这一问题显然属于求解最大独立集的问题。因此，最终的答案应为总格子数量减去损坏的格子数目再减去最大匹配值（即最小点覆盖数）。

    #include <bits/stdc++.h>