#include <iostream>
#define MAX 150
using namespace std;

int g[MAX][MAX];
int d[MAX][MAX];
int used[MAX][MAX];
int ans[MAX*MAX];
int use[MAX*MAX];
int num;
int k,x,y;
int n,m;
int dfs(int a) //dfs寻路
{ 
  int b;
  for(b=1;b<=num;b++)
   if (g[a][b]==1 && use[b]==0)
   {
		 use[b]=1;
         if (!ans[b]||dfs(ans[b])) 
		 {
			 ans[b]=a;
			 return 1;
		 }
    }
   return 0;
}
int main()
{
	int i,j;
	scanf("%d%d%d",&n,&m,&k);//原来写的是while(scanf(...)!=EOF)
	{
		memset(g,0,sizeof(g));
		memset(d,0,sizeof(d));
		memset(ans,0,sizeof(ans));
		memset(used,0,sizeof(used));
		for(i=0;i<k;i++)
		{
			scanf("%d%d",&y,&x);
			used[x][y]=1;
		}
		num=n*m-k;
		int z=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				if(!used[i][j])
					d[i][j]=z++;
		}
		for (i=1;i<=n;i++)
		{
		   for (j=1;j<=m;j++)
				if (!used[i][j])   //建图
				{ 
					 int t=d[i][j];
					 if (i-1>=1 && !used[i-1][j] ) 
						 g[t][d[i-1][j]]=1;
					 if (j-1>=1 && !used[i][j-1] ) 
						 g[t][d[i][j-1]]=1;
					 if (i+1<=n && !used[i+1][j] ) 
						 g[t][d[i+1][j]]=1;
					 if (j+1<=m && !used[i][j+1] ) 
						 g[t][d[i][j+1]]=1;
				} 
		}
	  
		for(i=1;i<=num;i++)
		{
			memset(use,0,sizeof(use));
			dfs(i);	  //寻路	 
		}
		int f=0;

		for(i=1;i<=num;i++)
		{
			if(ans[i]==0){f=1;cout<<"NO"<<endl;break;}//如果有没匹配上的
		}
		if(!f) cout<<"YES"<<endl;
	
	}
}

• 囧.....原来还是数组开小了.... (1578) c4pt0r 2008-07-13 11:02:45