二分匹配：构图很简单，注意构图的时候hole不能和其他的有边，设格子中2个格子x,y。x与y有一条边，y与x也有一条边，所以匹配数等于不是hole的个数。中间还可以判断不是hole的个数为奇数的时候直接输出NO，但好像时间少不了多少。

分别用了匈牙利算法（735+ms)和Hopcroft-Karp(157ms)算法

#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1230;
int d[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };
int distx[N], disty[N], matex[N], matey[N], q[N], f[N];
vector<int> g[N];

bool BFS( int n )
{
	bool found = false;
	int fore = 0, rear = 0;
	for ( int i = 0; i < n; ++i )
	{
		if ( matex[i] == -1 )
			q[rear++] = i;//加入队列
		distx[i] = 0;//要匹配的一边
		disty[i] = 0;//要匹配的另一边
	}
	for ( ; fore < rear; ++fore )//队列不空
	{
		int x = q[fore];//从队列从取出x，并扩展
		for ( vector<int>::const_iterator it = g[x].begin(); it != g[x].end(); ++it )
		{//
			if ( !disty[*it] )//选择未访问的点，因为是要求不相交的增广路径
			{
				disty[*it] = distx[x]+1;//至少是1，
				if ( matey[*it] == -1 )//为被匹配的自由点，未被访问过，说明找到一条路径
					found = true;
				else
				{
					distx[matey[*it]] = disty[*it]+1;
					q[rear++] = matey[*it];
				}
			}
		}
	}
	return found;
}

bool DFS( int x )
{
	for ( vector<int>::const_iterator it = g[x].begin(); it != g[x].end(); ++it )
		if ( disty[*it] == distx[x] + 1 )
		{//走了这条边，但是不一定是增广路径
			disty[*it] = 0;
			if ( matey[*it] == -1 || DFS( matey[*it] ) )
				return matex[x] = *it, matey[*it] = x, true;
		}
	return false;
}

int Hopcroft_Karp( int n )
{
	int res = 0;
	fill_n( matex, n, -1 );
	fill_n( matey, n, -1 );
	while ( BFS( n ) )
		for ( int i = 0; i < n; ++i )//可能存在多个增广路径
			if ( matex[i] == -1 && DFS( i ) )//找到了一个增广路径
				++res;
	return res;
}

int main()
{
	int n, m, k, x, y, xx, yy, t, tt, kk;
	memset( f, 0, sizeof( f ) );
	scanf( "%d%d%d", &m, &n, &k );
	kk = m * n - k;
	while ( k-- )
	{
        scanf( "%d%d", &x, &y );
		f[(y-1)*n+x-1] = 1;
	}
	for ( y = 0; y < m; ++y )
	for ( x = 0; x < n; ++x )
	{
		tt = y*n + x;
		if ( !f[tt] )
		for ( k = 0; k < 4; ++k )
		{
			xx = x+d[k][1]; yy = y+d[k][0];
			if ( xx >= 0 && xx < n && yy >= 0 && yy < m )
			{
				t = yy*n+xx;
				if ( f[t] == 0 ) g[tt].push_back( t );
			}
		}
	}
    if ( Hopcroft_Karp( m * n ) == kk )
		printf( "YES\n" );
	else
		printf( "NO\n" );
	return 0;
}

#include <stdio.h>
#include <string.h>
#define MAXN 1230 //X最大个数
#define MAXM 1230  //Y最大个数
int d[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };

char f[MAXN], path[MAXN][MAXM], visit[MAXM]; //path[i] [j]=true说明i到j有一条边
int match[MAXM]; //与Y中的点匹配的点标识
int SearchPath( int s, int m )
{
	int i;
	for ( i=0; i<m; i++ )
	{
		if ( path[s][i] && !visit[i] )//如果从s到i有边且Y中的i点没有被访问过
		{
			visit[i] = 1;
			if ( match[i]==-1 || SearchPath( match[i], m ) ) //查找可增广路并更新match数组
			{
				match[i] = s;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int n, m, k, x, y, xx, yy, t, tt, kk, sum, i;
	memset( f, 0, sizeof( f ) );
	memset( path, 0, sizeof( path ) ); //将二分图初始化
	memset( match, -1, sizeof( match ) ); //匹配数组初始化
	memset( visit, 0, sizeof( visit ) );
	scanf( "%d%d%d", &m, &n, &k );
	kk = m * n - k;
	if ( kk & 1 ) goto label;
	while ( k-- )
	{
        scanf( "%d%d", &x, &y );
		f[(y-1)*n+x-1] = 1;
	}
	for ( y = 0; y < m; ++y )
	for ( x = 0; x < n; ++x )
	{
		tt = y*n + x;
		if ( !f[tt] )
		for ( k = 0; k < 4; ++k )
		{
			xx = x+d[k][1]; yy = y+d[k][0];
			if ( xx >= 0 && xx < n && yy >= 0 && yy < m )
			{
				t = yy*n+xx;
				if ( f[t] == 0 ) path[tt][t] = 1;
			}
		}
	}
	n = n * m;
    for ( sum = i = 0; i < n; ++i )
	{
		memset( visit, 0, sizeof( visit ) ); //已经访问了的点初始化
		if ( SearchPath( i, n ) ) sum++;
	}
	if ( sum == kk )
		printf( "YES\n" );
	else
label:	printf( "NO\n" );
	return 0;
}