学步园

这个题郁闷了。。。

卡了好长时间，不过还好过了。将不相邻的点分为一组，也就是横纵坐标相加为奇数的为一组，另外为一组，然后相邻的在两组中间连一条线，最后求最大匹配

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};

struct node
{
    int no,x,y;
}left[52],right[52];
int n,m,k,cnt;
bool graph[52][52];
bool map[102][102];
int No[102][102];
int lcnt,rcnt;
bool vis[52];
int link[52];

bool find(int x)
{
    int y;
    for(y=1;y<=rcnt;y++)
    {
        int no=right[y].no;
        if(graph[x][no] && !vis[no])
        {
            vis[no]=true;
            if(!link[no] || find(link[no]))
            {
                link[no]=x;
                return true;
            }
        }
    }
    return false;
}


int main()
{
    int i,j,x,y;
    while(~scanf("%d%d",&n,&m) && (n+m))
    {
        scanf("%d",&k);
        cnt=lcnt=rcnt=0;
        memset(map,0,sizeof(map));
        memset(graph,0,sizeof(graph));
        memset(link,0,sizeof(link));
        memset(No,0,sizeof(No));
        for(i=1;i<=k;i++)
        {
            scanf("%d%d",&x,&y);
            map[x][y]=1;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(!map[i][j])
                {
                    No[i][j]=++cnt;
                    if((i+j)&1)
                    {
                        left[++lcnt].no=cnt;
                        left[lcnt].x=i;
                        left[lcnt].y=j;
                    }
                    else
                    {
                        right[++rcnt].no=cnt;
                        right[rcnt].x=i;
                        right[rcnt].y=j;
                    }
                }
            }
        }
        for(i=1;i<=lcnt;i++)
        {
            for(j=0;j<4;j++)
            {
                //printf("no:%d   x:%d  y:%d \n",left[i].no,left[i].x,left[i].y);
                int nx=left[i].x+dx[j];
                int ny=left[i].y+dy[j];
                if(No[nx][ny]!=0)
                {
                    //printf("    nx:%d   ny:%d   no:%d\n",nx,ny,No[nx][ny]);
                    graph[left[i].no][No[nx][ny]]=1;
                }
            }
        }
//        for(i=1;i<=lcnt;i++)
//        {
//            printf("left %d  %d  %d \n",left[i].no,left[i].x,left[i].y);
//        }
//        for(i=1;i<=50;i++)
//        {
//            for(j=1;j<=50;j++)
//                if(graph[i][j])
//                    printf("link   %d    %d \n",i,j);
//        }
        int ans=0;
        for(i=1;i<=lcnt;i++)
        {
            memset(vis,0,sizeof(vis));
            if(find(left[i].no))
                ans++;
        }
        printf("%d\n",ans);
        for(i=1;i<=rcnt;i++)
        {
            int no=right[i].no;
            if(link[no])
            {
                for(j=1;j<=lcnt;j++)
                {
                    if(left[j].no==link[no])
                        printf("(%d,%d)--(%d,%d)\n",left[j].x,left[j].y,right[i].x,right[i].y);
                }
            }
        }
        puts("");
    }
    return 0;
}