学步园

题目链接:   uva 12530

题目大意:   给出50x50的地图，地图上某些点不能走，可以走四个方向

                  Alice选任意一个点开始，然后和Bob轮流走，重复的点不能走

                  最后轮到谁走却不能移动棋子就输

解题思路:   二分图的完美匹配：最大匹配数刚好覆盖完左右集合的顶点

                  若图存在完美匹配，先手选择任意点，后手都选择与其匹配的点，先手必输

                  若图不存在完美匹配，先手选择不属于最大匹配的点，先手必胜

                  找出所有的连通块，进行黑白染色，即选择某点染黑，周围点染白

                  判断是否有一个块不存在完美匹配的，若存在先手选它则必胜

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 53
char Map[MAX][MAX];
int Co[MAX][MAX],F[MAX][MAX],n,m,an;
int cx[MAX*MAX],cy[MAX*MAX],visit[MAX*MAX],Index;
int Fx[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct snode{
    int x,y;
}ans[MAX*MAX];

struct node{
    int to,next;
}Edge[100000];

int pre[MAX*MAX];

void Add_edge(int a,int b)
{
    Edge[Index].to=b;
    Edge[Index].next=pre[a];
    pre[a]=Index++;
}

void Color(int x,int y,int k)  //不同的连通块黑白染色
{
    int i,xx,yy;
    Map[x][y]='X';
    Co[x][y]=k;
    ans[an].x=x,ans[an++].y=y;
    F[x][y]=an;
    for(i=0;i<4;i++)
    {
        xx=Fx[i][0]+x;
        yy=Fx[i][1]+y;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&Map[xx][yy]=='.')
            Color(xx,yy,-k);
    }
}

int DFS(int u,int an)   //匈牙利最大匹配
{
    int i,v;
    for(i=pre[u];i!=-1;i=Edge[i].next)
    {
        v=Edge[i].to;
        if(!visit[v])
        {
            visit[v]=1;
            if(!cy[v]||DFS(cy[v],an))
            {
                cx[u]=v;
                cy[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int Solve()
{
    int i1,j1,x,y,xx,yy,t;
    Index=0;                      //***
    memset(pre,-1,sizeof(pre));
    for(i1=0;i1<an;i1++)
    {
        x=ans[i1].x;
        y=ans[i1].y;
        t=Co[x][y];
        for(j1=0;j1<4;j1++)
        {
            xx=Fx[j1][0]+x;
            yy=Fx[j1][1]+y;
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&Co[xx][yy]==-t)
            {
                Add_edge(F[x][y],F[xx][yy]);           //***
                Add_edge(F[xx][yy],F[x][y]);           //***
            }
        }
    }
    memset(cx,0,sizeof(cx));
    memset(cy,0,sizeof(cy));
    for(i1=1,t=0;i1<=an;i1++)
    {
        if(!cx[i1])               //x匹配y
        {
            memset(visit,0,sizeof(visit));
            t+=DFS(i1,an);        //增广轨
        }
    }
    if(t==an)  //当t==an时候，存在完美匹配
        return 0;
    return 1;
}

int main()
{
    int i,j,k,pd;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        gets(Map[1]+1);
        memset(F,0,sizeof(F));
        memset(Map,'X',sizeof(Map));
        memset(Co,0,sizeof(Co));
        for(i=1;i<=n;i++)
            gets(Map[i]+1);
        k=0; pd=0;
        for(i=1;i<=n&&!pd;i++)
        {
            for(j=1;j<=m&&!pd;j++)
            {
                if(Map[i][j]=='.')
                {
                    an=0; ++k;   //
                    Color(i,j,k);
                    pd=Solve();
                }
            }
        }
        if(pd==1)
            printf("1\n");
        else
            printf("2\n");
    }
    return 0;
}