#include<stdio.h>
#include<string.h>
#include <iostream>
#include<algorithm>
using namespace std;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool vis[1200],edge[1200][1200];
int point[1200],rea[1200];
int n,m,t,num;
bool go(int x,int y)
{
	if(x>=1&&y>=1&&x<=n&&y<=m&&edge[x][y])
		return 1;
		return 0;
}
bool dfs(int p)
{
	int k,x,y,nextp;
	for(k=0;k<4;k++)
	{
	  x=p/33+dir[k][0],y=p%33+dir[k][1],nextp=x*33+y;
		if(go(x,y)&&!vis[nextp])
		{
			vis[nextp]=true;
			if(rea[nextp]==-1||dfs(rea[nextp]))
			{
				rea[nextp]=p;
				return 1;
			} 
		}
	}
	return 0;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
	if((n*m-t)%2==1)
	{
		puts("NO");
		continue;
	}
int i,j,x,y;
  memset(rea,-1,sizeof(rea));
  memset(edge,true,sizeof(edge));	
	while(t--)
	{
		scanf("%d%d",&x,&y);
		edge[y][x]=false;
	}
  num=0;
  for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		{
			if((i+j)%2==0&&edge[i][j])
				point[++num]=i*33+j;
		 }
  int ans=0;
  for(i=1;i<=num;i++)
  {
	 memset(vis,0,sizeof(vis));
	if(dfs(point[i]))
		ans++;
  }	
  if(ans==num)
	  puts("YES");
  else 
	  puts("NO");
 }
return 0;
}

• Re:0ms代码。 (30) yinqingwang 2012-06-08 20:29:54