HDU 3446 daizhenyang's chess

http://acm.hdu.edu.cn/showproblem.php?pid=3446

题意:一个棋盘，有个KING，有一些能走的点，每次只能走到没走过的地方，没路可走的输，求先手是否必胜。

思路:先去掉KING的位置，只考虑其他的，如果这样求出的匹配数和加上king的匹配数一样，说明KING这个位置没有在匹配中，因此后手必胜，否则先手必胜，为什么？

可以思考一下，匹配的路径是一条:匹配，不匹配，匹配。。。不匹配，匹配，因此如果KING在匹配中，那最后一步也能够是先手走的。

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

int dx[]={-,-,-,,,,,,,-,,-,,-,,-,,-,-,};

int dy[]={-,,,,,-,-,,,,-,-,,-,-,,,-,,-};

int match[],G[][],inpath[],q[],head,tail,newbase;

int inqueue[],inblossom[],base[],father[],n;

int finish,start,R,C,kx,ky,c[];

char s[][];

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

int lca(int u,int v){

    memset(inpath,,sizeof inpath);

    while (){

        u=base[u];

        inpath[u]=;

        if (!match[u]) break;

        u=father[match[u]];

    }

    while (){

        v=base[v];

        if (inpath[v]) break;

        v=father[match[v]];

    }

    return v;

}

void reset(int u){

    while (u!=newbase){

        int v=match[u];

        inblossom[base[v]]=inblossom[base[u]]=;

        u=father[v];

        if (base[u]!=newbase) father[u]=v;

    }

}

void blossomcontract(int u,int v){

    newbase=lca(u,v);

    memset(inblossom,,sizeof inblossom);

    reset(u);

    reset(v);

    if (base[u]!=newbase) father[u]=v;

    if (base[v]!=newbase) father[v]=u;

    for (int i=;i<=n;i++)

     if (inblossom[base[i]]){

            base[i]=newbase;

            if (!inqueue[i]) c[++tail]=i,inqueue[i]=;

     }

}

void findaugmentingpath(){

    memset(inqueue,,sizeof inqueue);

    memset(father,,sizeof father);

    for (int i=;i<=n;i++) base[i]=i;

    head=;tail=;c[]=start;inqueue[start]=;

    finish=;

    while (head<=tail){

        int u=c[head++];

        for (int v=;v<=n;v++)

         if (G[u][v]&&base[u]!=base[v]&&match[v]!=u){

                if (v==start||(match[v]>)&&(father[match[v]]>)){

                    blossomcontract(u,v);

                }else

                if (father[v]==){

                    father[v]=u;

                    if (match[v]){

                        c[++tail]=match[v];inqueue[match[v]]=;

                    }else{

                        finish=v;

                        return;

                    }

                }

         }

    }

}

void augmentpath(){

    int u,v,w;

    u=finish;

    while (u>){

        v=father[u];

        w=match[v];

        match[u]=v;

        match[v]=u;

        u=w;

    }

}

int solve(){

    int res=;

    memset(match,,sizeof match);

    for (int i=;i<=n;i++)

     if (!match[i]){

        start=i;

        findaugmentingpath();

        if (finish) augmentpath(),res++;

     }

    return res;

}

int main(){

    int T=read(),Tcase=;

    while (T--){

        printf("Case #%d: daizhenyang ",++Tcase);

        R=read();C=read();

        memset(G,,sizeof G);

        for (int i=;i<=R;i++){

            scanf("%s",s[i]+);

        }

        for (int i=;i<=R;i++)

         for (int j=;j<=C;j++)

          if (s[i][j]!='#'){

           for (int k=;k<;k++){

                int x=i+dx[k],y=j+dy[k];

                if (x>=&&x<=R&&y>=&&y<=C&&s[x][y]!='#'){

                    G[(i-)*C+j][(x-)*C+y]=;

                    G[(x-)*C+y][(i-)*C+j]=;

                }

           }

           if (s[i][j]=='K') kx=i,ky=j;

          }

        n=R*C;

        int t1=solve();

        int x=(kx-)*C+ky;

        for (int i=;i<=n;i++) if (G[x][i]) G[x][i]=G[i][x]=;

        if (solve()==t1) puts("lose");

        else puts("win");

    }

    return ;

}