思路：由(i+j)为偶数的点向(i+j)为奇数的点建边。求一次最大匹配，若正好为空格数(不包含洞)的一半，即输出YES。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define Maxn 1101 using namespace std; int n,m,vi[Maxn],match[Maxn],graphic[Maxn][Maxn],map[40][40],N[Maxn],M[Maxn],x,y; int dfs(int u) { int i; for(i=1;i<=y;i++) { if(!vi[M[i]]&&graphic[u][M[i]]) { vi[M[i]]=1; if(match[M[i]]==-1||dfs(match[M[i]])) { match[M[i]]=u; return 1; } } } return 0; } int Pos(int i,int j) { return (i-1)*n+j; } int main() { int i,j,t,a,b,k; while(scanf("%d%d%d",&m,&n,&k)!=EOF) { memset(match,-1,sizeof(match)); memset(graphic,0,sizeof(graphic)); memset(map,0,sizeof(map)); for(i=1;i<=k;i++) { scanf("%d%d",&a,&b); map[b][a]=1; } x=y=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if((i+j)%2) M[++y]=Pos(i,j); else N[++x]=Pos(i,j); if(j<n) { if(!map[i][j+1]&&!map[i][j]) { if((i+j)%2==0) graphic[Pos(i,j)][Pos(i,j+1)]=1; if((i+j)%2) { graphic[Pos(i,j+1)][Pos(i,j)]=1; } } } if(i<m) { if(!map[i+1][j]&&!map[i][j]) { if((i+j)%2) graphic[Pos(i+1,j)][Pos(i,j)]=1; if((i+j)%2==0) graphic[Pos(i,j)][Pos(i+1,j)]=1; } } } } int ans=n*m-k; if(ans%2==1) { printf("NO "); continue; } int num=0; for(i=1;i<=x;i++) { memset(vi,0,sizeof(vi)); if(dfs(N[i])) { num++; } } if(num*2==ans) printf("YES "); else printf("NO "); } return 0; }