【题解】JSOI2009游戏

真的没想到、、、果然反应太迟钝，看到题目毫无思路，一点联想都没有。

按照网上博客的说法：一眼棋盘染色二分->二分图->最大匹配->BINGO?果然我还是太弱了……

我们将棋盘黑白染色，相邻两点之间的转移转化为图上的边。根据最大匹配的定义，如果我们最开始将棋子放在一个未匹配的点上，一定会到达一个匹配点（不然若到达了另一个未匹配点就说明还有可以扩张的匹配。）此后，因为已经是最大匹配所以不存在可以增广的交替路。所以这样先手一定会比后手多走一步，获得胜利。所以问题转化为：有哪些点不在最大匹配上？注意最大匹配的情况数是很多的。

所以我们枚举每一个点是否可以不被纳入最大匹配，若可以，说明是一个先手必胜点。

#include <bits/stdc++.h>

using namespace std;

#define maxn 205

int n, m, a[maxn][maxn], link[maxn * ];

int Map[maxn * ][], ans[maxn * ][];

int cnt, tot, id[maxn][maxn];

int px[] = { , , -,  }, py[] = { , , , - };

bool vis[maxn * ];

char s[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

bool dfs(int u)

{

    for(int i = ; i <= Map[u][]; i ++)

    {

        int v = Map[u][i];

        if(vis[v]) continue; vis[v] = ;

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

            { link[v] = u, link[u] = v; return ; }

    }

    return ;

}

void add(int u, int v) { Map[u][++ Map[u][]] = v; }

int main()

{

    n = read(), m = read();

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

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

            id[i][j] = ++ cnt;

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

    {

        scanf("%s", s + );

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

            if(s[j] == '#') a[i][j] = ;

    }

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

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

            if(!a[i][j] && (i + j) % )

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

                {

                    int mx = i + px[k], my = j + py[k];

                    if(mx >=  && mx <= n && my >=  && my <= m && !a[mx][my])

                    {

                        add(id[i][j], id[mx][my]);

                        add(id[mx][my], id[i][j]);

                    }

                }

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

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

            if(!a[i][j] && (i + j) % )

            {

                memset(vis, , sizeof(vis));

                if(dfs(id[i][j])) cnt ++;

            }

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

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

            if(!a[i][j])

            {

                memset(vis, , sizeof(vis)); vis[id[i][j]] = ;

                if(!link[id[i][j]] || dfs(link[id[i][j]]))

                {

                    ans[++ tot][] = i, ans[tot][] = j;

                    link[id[i][j]] = ;

                }

            }

    if(!tot) printf("LOSE");

    else

    {

        printf("WIN\n");

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

            printf("%d %d\n", ans[i][], ans[i][]);

    }

    return ;

}