#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
typedef struct node
{
	int x,y;
}node;
int p[33][33];
int visit[33][33];
node link[33][33];
int n,m,k;
int num;
int f[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int dfs(int i,int j)
{
	int k;
	int x,y;
	for(k=0;k<4;k++)
	{
		x=i+f[k][0];
		y=j+f[k][1];
		if(x>=1&&x<=n&&y>=1&&y<=m)
		{
			if(!p[x][y]&&!visit[x][y])
			{
				visit[x][y]=1;
				if((link[x][y].x==-1&&link[x][y].y==-1)||dfs(link[x][y].x,link[x][y].y))
				{
					link[x][y].x=i;
					link[x][y].y=j;
					return 1;
				}
			}
		}
	}
	return 0;
}

int func()
{
	int i,j;
	memset(link,-1,sizeof(link));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(!p[i][j])
			{
				if((n%2==1&&((i-1)*n+j)%2==1)||(n%2==0&&((i%2)==(j%2))))
				{
					memset(visit,0,sizeof(visit));
					if(dfs(i,j))
					num++;
				}
			}
		}
	}
	if(2*num+k==n*m)
		return 1;
	else
		return 0;
}

int main (void)
{
	int i;
	int x,y;
	int flag;
	scanf("%d %d %d",&n,&m,&k);
	if((n*m-k)%2)
	{
		printf("NO\n");
		return 1;
	}
	for(i=1;i<=k;i++)
	{
		scanf("%d %d",&y,&x);
		p[x][y]=1;
	}
	flag=func();
	if(flag)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

• Re 对的，这样看是否存在一个完备匹配; (1436) yuanchuanshun 2012-03-18 09:50:14