题目链接：
?id=2446
题目大意：
给一个N*M的矩阵，其中有K个地方有坑。告诉你这K个坑的位置，现在要用1*2的矩形板去覆盖
矩阵，不能覆盖有坑的地方。问：是否能把除了坑之外的地方全部覆盖掉，，如果能，则输出"YES",
否则输出"NO"。
思路：
考虑到矩形板的规格是1*2，则相邻位置的(i，j)和(x，y)必然是(i+j)为奇数的话，(x+y)则为偶数。
(i+j)为偶数的话，(x+j)则为奇数。这样，就可以把图上的所有点分为横纵坐标相加为奇数的点和
横纵坐标相加为偶数的点。然后建立一个二分图，一边为奇数点，另一边为偶数点。如果能用矩
形板覆盖(即没有坑)，则在二分图上加边。然后求出二分图最大匹配ans，也就是最多能覆盖多少
矩形板。因为每个矩形板的规格是1*2，所以要判断是否能把除了坑之外的全部地方覆盖掉，只需
要判断ans*2 + K 是否等于M*N即可。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 33;const int MAXM = 1100;bool Map[MAXM][MAXM],Mask[MAXM];int NX,NY;int cx[MAXM],cy[MAXM];int G[MAXN][MAXN];int FindPath(int u){for(int i = 1; i <= NY; ++i){if(Map[u][i] && !Mask[i]){Mask[i] = 1;if(cy[i] == -1 || FindPath(cy[i])){cy[i] = u;cy[u] = i;return 1;}}}return 0;}int MaxMatch(){for(int i = 1; i <= NX; ++i)cx[i] = -1;for(int i = 1; i <= NY; ++i)cy[i] = -1;int res = 0;for(int i = 1; i <= NX; ++i){if(cx[i] == -1){for(int j = 1; j <= NY; ++j)Mask[j] = 0;res += FindPath(i);}}return res;}int main(){int N,M,K,u,v;while(~scanf("%d%d%d",&N,&M,&K)){memset(Map,0,sizeof(Map));memset(G,0,sizeof(G));for(int i = 1; i <= K; ++i){scanf("%d%d",&u,&v);G[u][v] = -1;}int Num1,Num2;Num1 = Num2 = 1;for(int i = 1; i <= N; ++i){for(int j = 1; j <= M; ++j){if(G[i][j] == 0){if((i+j)&1)G[i][j] = Num1++;elseG[i][j] = Num2++;}}}for(int i = 1; i <= N; ++i){for(int j = 1; j <= M; ++j){if(G[i][j] != -1 && (i+j)&1){if(G[i-1][j] >= 1)Map[G[i-1][j]][G[i][j]] = 1;if(G[i+1][j] >= 1)Map[G[i+1][j]][G[i][j]] = 1;if(G[i][j-1] >= 1)Map[G[i][j-1]][G[i][j]] = 1;if(G[i][j+1] >= 1)Map[G[i][j+1]][G[i][j]] = 1;}}}NX = Num1;NY = Num2;int ans = MaxMatch();if(ans*2 + K == M*N)printf("YES\n");elseprintf("NO\n");}return 0;}
以诚感人者，人亦诚而应。
