学步园

解法：黑白染色法！！

#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
const int maxn=10002;
int f[maxn][6],mat[maxn],vis[maxn],n,m;
int map[102][102];
int dx[5]= {1,-1,0,0};
int dy[6]= {0,0,-1,1};
int list[maxn];
///邻接表 实现匈牙利算法
int idx,num,link;
int inmap(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m)return 1;
    return 0;
}
int find(int x)
{
    for(int i=f[x][0]; i>=1; i--)
    {
        int y=f[x][i];
        if(!vis[y])
        {
            vis[y]=1;
            if(mat[y]==-1||find(mat[y]))
            {
                mat[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,k,t,ans,xi,yi;
    while(scanf("%d%d",&n,&m),(n||m))
    {
        memset(f,0,sizeof(f));
        memset(mat,-1,sizeof(mat));
        memset(map,1,sizeof(map));
        int cnt=0;
        ans=0;
        scanf("%d",&k);
        for(i=1; i<=k; i++)
        {
            scanf("%d %d",&xi,&yi);
            map[xi][yi]=0;
        }
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                if(map[i][j]&&(i+j)%2==0)
                {
                    int flag=0;
                    for(t=0; t<4; t++)
                    {
                        int x=i+dx[t];
                        int y=j+dy[t];
                        if(inmap(x,y)&&map[x][y])
                        {
                            flag=1;
                            f[(i-1)*m+j][++f[(i-1)*m+j][0]]=(x-1)*m+y;
                        }
                    }
                    if(flag)list[cnt++]=(i-1)*m+j;
                }
            }
        }
        for(i=0; i<cnt; i++)
        {
            int x=(list[i]+m-1)/m;
            int y=list[i]-x;
            memset(vis,0,sizeof(vis));
            if(find(list[i])) ans++;
        }
        printf("%d\n",ans);
        for(i=2; i<=m*n; i++)
        {
            int x=(i+m-1)/m;
            int y=i-(x-1)*m;
            if(mat[i]>0)
            {
               // cout<<mat[i]<<endl;
              //  system("pause");
                int x1=(mat[i]+m-1)/m;
                int y1=mat[i]-(x1-1)*m;
                printf("(%d,%d)--(%d,%d)\n",x1,y1,x,y);
            }
        }
        printf("\n");
    }
    return 0;
}