#include<iostream>
using namespace std;
int n,m,k,map[1000][1000],v[1000],mmax,match[1000],g[155][155];
void init()
{
	memset(g,0,sizeof(g));
	memset(match,0xff,sizeof(match));
	memset(map,0,sizeof(map));
}
void resetV()
{
	memset(v,0,sizeof(v));
}
int dfs(int q)
{
	int i,t,ind,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if((i+j)%2==1){
				ind=(i-1)*m+j;
				if(map[q][ind] && !v[ind])
				{	
					v[ind]=1;
					t=match[ind];
					match[ind]=q;
					if(t<0 || dfs(t))return 1;
					match[ind]=t;
				}
			}
	return 0;
}
int main()
{
	int i,r,c,ind,j,res;
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
		mmax=n*m;
		init();
		for(i=0;i<k;i++){
			scanf("%d%d",&r,&c),
			g[c][r]=1;
		}
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(g[i][j])continue;				
				ind=(i-1)*m+j;
				if((i+j)%2==0){
					if(i<n && g[i+1][j]==0)map[ind][ind+m]=1;
					if(i>1 && g[i-1][j]==0)map[ind][ind-m]=1;
					if(j>1 && g[i][j-1]==0)map[ind][ind-1]=1;
					if(j<m && g[i][j+1]==0)map[ind][ind+1]=1;
				}
			}
		res=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++){
				if((i+j)%2==0 && g[i][j]==0)
				{
					resetV();
					ind=(i-1)*m+j;
					if(dfs(ind))res++;
				}
			}
		if(res*2==mmax-k)puts("YES");
		else puts("NO");
	}
	return 0;
}

• Re:为啥一直过不了。。。 (41) notwhile 2009-07-21 17:11:36
  • Re:为啥一直过不了。。。 (58) phoenixwright 2009-07-21 18:49:57