思路：由(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[][],N[Maxn],M[Maxn],x,y;
int dfs(int u)
{
int i;
for(i=;i<=y;i++)
{
if(!vi[M[i]]&&graphic[u][M[i]])
{
vi[M[i]]=;
if(match[M[i]]==-||dfs(match[M[i]]))
{
match[M[i]]=u;
return ;
}
}
}
return ;
}
int Pos(int i,int j)
{
return (i-)*n+j;
}
int main()
{
int i,j,t,a,b,k;
while(scanf("%d%d%d",&m,&n,&k)!=EOF)
{ memset(match,-,sizeof(match));
memset(graphic,,sizeof(graphic));
memset(map,,sizeof(map));
for(i=;i<=k;i++)
{
scanf("%d%d",&a,&b);
map[b][a]=;
}
x=y=;
for(i=;i<=m;i++)
{
for(j=;j<=n;j++)
{
if((i+j)%)
M[++y]=Pos(i,j);
else
N[++x]=Pos(i,j);
if(j<n)
{
if(!map[i][j+]&&!map[i][j])
{
if((i+j)%==)
graphic[Pos(i,j)][Pos(i,j+)]=;
if((i+j)%)
{
graphic[Pos(i,j+)][Pos(i,j)]=;
}
}
}
if(i<m)
{
if(!map[i+][j]&&!map[i][j])
{
if((i+j)%)
graphic[Pos(i+,j)][Pos(i,j)]=;
if((i+j)%==)
graphic[Pos(i,j)][Pos(i+,j)]=;
}
}
}
}
int ans=n*m-k;
if(ans%==)
{
printf("NO\n");
continue;
}
int num=;
for(i=;i<=x;i++)
{
memset(vi,,sizeof(vi));
if(dfs(N[i]))
{
num++;
}
}
if(num*==ans)
printf("YES\n");
else
printf("NO\n"); }
return ;
}