[JSOI2009]游戏Game

Description

Input

输入数据首先输入两个整数N,M，表示了迷宫的边长。 接下来N行，每行M个字符，描述了迷宫。

Output

若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出 每行一个,否则输出一行"LOSE"（不包含引号）。

Sample Input

3 3
.##
...
#.#

Sample Output

WIN
2 3
3 2

HINT

对于100%的数据，有1≤n,m≤100。 对于30%的数据，有1≤n,m≤5。

这道题和[NOI2011]兔兔与蛋蛋游戏很像

首先黑白染色

同样的，对于一个点，如果它不一定构成最大匹配

也就是ban掉该点后还有最大匹配

那么它就是后手必胜

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 struct Node

 {

   int next,to;

 }edge[];

 int head[],num,n,m,x,y,id[][],cnt,cx[],tot;

 bool vis[];

 char s[];

 void add(int u,int v)

 {

   num++;

   edge[num].next=head[u];

   head[u]=num;

   edge[num].to=v;

 }

 bool dfs(int x)

 {int i;

   for (i=head[x];i;i=edge[i].next)

     {

       int v=edge[i].to;

       if (vis[v]==)

     {

       vis[v]=;

       if (!cx[v]||dfs(cx[v]))

         {

           cx[x]=v;cx[v]=x;

           return ;

         }

     }

     }

   return ;

 }

 int main()

 {int i,j,flag=;

   cin>>n>>m;

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

     {

       scanf("%s",s+);

       for (j=;j<=m;j++)

     {

       if (s[j]=='.') id[i][j]=++cnt;

     }

     }

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

     {

       for (j=;j<=m;j++)

     if (id[i][j])

       {

         if (i>&&id[i-][j]) add(id[i][j],id[i-][j]);

         if (i<n&&id[i+][j]) add(id[i][j],id[i+][j]);

         if (j>&&id[i][j-]) add(id[i][j],id[i][j-]);

         if (j<m&&id[i][j+]) add(id[i][j],id[i][j+]);

       }

     }

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

     {

       for (j=;j<=m;j++)

     if (id[i][j]&&(i+j)%)

       {

         memset(vis,,sizeof(vis));

         dfs(id[i][j]);

       }

     }

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

     {

       for (j=;j<=m;j++)

     if (id[i][j])

     {

           memset(vis,,sizeof(vis));

           int u=id[i][j],v=cx[id[i][j]];

            vis[u]=;

           if (!cx[u]||dfs(v))

         {

           cx[u]=;

           if (flag==)

             cout<<"WIN\n";

           flag=;

           printf("%d %d\n",i,j);

         }

     }

     }

   if (flag==) cout<<"LOSE";

 }

[JSOI2009]游戏Game的相关教程结束。