POJ2446

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
bool a[2001][2001],vis[2001],mp[2001][2001];
int ans,n,m,k,dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}},ma[2001];
bool find(int now){
	for(int i=1;i<=n*m;i++){
		if(!mp[i][now]||vis[i])continue;
		vis[i]=1;
		if(!ma[i]||find(ma[i])){
			ma[i]=now;
			return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	if((n*m-k)%2==1){
		puts("NO");
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<4;k++){
				int x=i+dir[k][0],y=j+dir[k][1];
				if(x<1||y<1||x>n||y>m)continue;
				if(a[i][j]||a[x][y])continue;
				mp[(i-1)*m+j][(x-1)*m+y]=1;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(a[i][j]||(i+j)%2==1)continue;
			memset(vis,0,sizeof vis);
			ans+=find((i-1)*m+j);
		}
	if(ans*2+k==n*m)puts("YES");
	else puts("NO");
	return 0;
}

WA了