Sgu/190

无聊的匹配……

有点意思的题。。
/by Logic
#include<stdio.h>
#include<string.h>
const int maxn=45;
int n,p,ansh=0,ansv,ans[maxn*maxn];
int vis[maxn][maxn]={0},s[2]={0},z=0;
int f[maxn*maxn]={0};
bool vism[maxn*maxn]={0};
int di[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void dfs(int x,int y,int c)
{
	int i;
	vis[x][y]=c;
	s[c-1]++;
	for(i=0;i<4;i++)
	{
		int xi=x+di[i][0],yi=y+di[i][1];
		if(0<xi&&xi<=n&&0<yi&&yi<=n&&vis[xi][yi]!=-1)
		{
			if(!vis[xi][yi])
				dfs(xi,yi,(c&1)+1);
			else if(vis[xi][yi]==vis[x][y]) {z=1;return ;}
		}
	}
}
bool match(int now)
{
	int i,j,x=now/maxn,y=now%maxn;
	if(vism[now]) return 0;
	vism[now]=1;
	for(i=0;i<4;i++)
	{
		int xi=x+di[i][0],yi=y+di[i][1];
		if(0<xi&&xi<=n&&0<yi&&yi<=n&&vis[xi][yi]!=-1&&(!f[xi*maxn+yi]||match(f[xi*maxn+yi])))
			{
				f[xi*maxn+yi]=x*maxn+y;
				return 1;
			}
	}
	return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i,j,x,y;
	scanf("%d%d",&n,&p);
	for(i=0;i<p;i++)
		scanf("%d%d",&x,&y),vis[x][y]=-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(!vis[i][j])
				dfs(i,j,1);
	//printf("%d %d\n",s[0],s[1]);
	if(z||s[0]!=s[1]) {printf("No\n");return 0;}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(vis[i][j]==1)
			{
				memset(vism,0,sizeof(vism));
				if(!match(i*maxn+j)) {z=1;break;}
			}
	if(z) {printf("No\n");return 0;}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(f[i*maxn+j]==(i+1)*maxn+j)
				ans[ansh++]=i*maxn+j;
			else if(f[i*maxn+j]==(i-1)*maxn+j)
				ans[ansh++]=(i-1)*maxn+j;
	ansv=ansh;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(f[i*maxn+j]==i*maxn+j+1)
				ans[ansv++]=i*maxn+j;
			else if(f[i*maxn+j]==i*maxn+j-1)
				ans[ansv++]=i*maxn+j-1;
	printf("Yes\n%d\n",ansh);
	for(i=0;i<ansh;i++)
		printf("%d %d\n",ans[i]/maxn,ans[i]%maxn);
	printf("%d\n",ansv-ansh);
	for(i=ansh;i<ansv;i++)
		printf("%d %d\n",ans[i]/maxn,ans[i]%maxn);
	return 0;
}

//我猥琐的用了STL。
//BY Noise
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int gt[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct pr{int x,y;};
vector <pr> bk,wt;
int map[42][42],n,p,dx[42][42],dy[42][42];
bool bl[42][42];
bool find(int x,int y)
{
	for(int i=0;i<4;i++){
	  int x1=x+gt[i][0],y1=y+gt[i][1];
	  if(map[x1][y1])continue;
	  if(!bl[x1][y1])continue;
	  bl[x1][y1]=false;
	  if(dx[x1][y1]==0||find(dx[x1][y1],dy[x1][y1])){
	    dx[x1][y1]=x;dy[x1][y1]=y;return true;
	  }
	}
	return false;
}
int main()
{
	int i,j,a,b;
	scanf("%d%d",&n,&p);
	for(i=0;i<=n+1;i++)map[0][i]=map[i][0]=map[n+1][i]=map[i][n+1]=1;
	for(i=1;i<=p;i++){
	  scanf("%d%d",&a,&b);
	  map[a][b]=1;
	}
	for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++){
	    if(map[i][j])continue;
	    pr q;
	    q.x=i;q.y=j;
	    if((i+j)&1)bk.push_back(q);
	      else wt.push_back(q);
	  }
	if(bk.size()!=wt.size()){printf("No\n");return 0;}
	for(i=0;i<bk.size();i++){
	  memset(bl,true,sizeof(bl));
	  if(!find(bk[i].x,bk[i].y)){printf("No\n");return 0;}
	}
	printf("Yes\n");
	vector<int> c,r;
	for(i=0;i<wt.size();i++){
	  int x=wt[i].x,y=wt[i].y;
	  if(dx[x][y]==x)r.push_back(i);
	  else c.push_back(i);
	}
	printf("%d\n",c.size());
	for(i=0;i<c.size();i++){
	  int num=c[i];
          int x=wt[num].x,y=wt[num].y;
	  printf("%d %d\n",min(x,dx[x][y]),y);
	}
	printf("%d\n",r.size());
	for(i=0;i<r.size();i++){
	  int num=r[i];int x=wt[num].x,y=wt[num].y;
	  printf("%d %d\n",x,min(y,dy[x][y]));
	}
	return 0;
}