题目描述

小AA和小YY得到了《喜羊羊和灰太狼》的电影票，都很想去观看，但是电影票只有一张，于是他们用智力游戏决定胜负，赢得游戏的人可以获得电影票。

在N*M的迷宫中有一个棋子，小AA首先任意选择棋子放置的位置。然后，小YY和小AA轮流将棋子移动到相邻的格子里。游戏的规则规定，在一次游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。

例如下图所示的迷宫，迷宫中”.”表示棋子可以经过的格子，而”#”表示棋子不可以经过的格子：

.##
…

.

若小AA将棋子放置在(1,1)，则小 AA 则无论如何都无法赢得游戏。

而若小AA将棋子放置在(3,2)或(2,3)，则小AA能够赢得游戏。例如，小AA将棋子放置在(3,2)，小YY只能将它移动到(2,2)，此时小AA再将棋子移动到(2,3)，就赢得了游戏。

小AA和小YY都是绝顶聪明的小朋友，且从不失误。小AA到底能不能赢得这场游戏，从而得到珍贵的电影票呢？

输入格式

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

输出格式

若小 AA 能够赢得游戏，则输出一行”WIN”，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出，每行一个。

否则输出一行”LOSE”（不包含引号）。

输入样例

3 3
.##
…

.

输出样例

WIN
2 3
3 2

说明

对30%的数据，有1<=n,m<=5

对100%的数据，有1<=n,m<=100

Solution

这道题我么可以进行黑白染色，然后连边用最大流跑最大匹配，如果是完美匹配就无论如何小A也无法胜利，否则，就会出现一些小A能到达的点但是小Y却无法到达。

~~输出方案害死人~~

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
#define MAXN 10010001
#define INF 2000000000
struct Edge {
    int v, nx, w;
}e[MAXN];
int min(int a, int b) {
    if (a < b) return a;
    else return b;
}
int head[MAXN], ecnt = 1, n, m, x, y, dep[MAXN], cur[MAXN], map[210][210], wb[210][210], r, k, cnt;
int find[MAXN];
bool vis[MAXN], wh[MAXN];
void add(int f, int t, int w) {
    e[++ecnt] = (Edge) {t, head[f], w};
    head[f] = ecnt;
    e[++ecnt] = (Edge) {f, head[t], 0};
    head[t] = ecnt;
}
int g(int i, int j) {
    return (i - 1) * m + j;
}
std::queue <int> q;
bool bfs(int s, int t) {
    memset(dep, 0x7f, sizeof(dep));
    dep[s] = 0;
    while (!q.empty()) q.pop();
    q.push(s);
    for (int i = 1; i <= n * m + 2; i++) {
        cur[i] = head[i];
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nx) {
            int to = e[i].v;
            if (dep[to] > INF && e[i].w) {
                dep[to] = dep[u] + 1;
                q.push(to);
            }
        }
    }
    if (dep[t] > INF) return 0;
    else return 1;
}
int dfs(int s, int t, int l) {
    if (!l || s == t) return l;
    int fl = 0, f;
    for (int i = cur[s]; i; i = e[i].nx) {
        int to = e[i].v;
        cur[s] = i;
        if (dep[to] == dep[s] + 1 && (f = dfs(to, t, min(l, e[i].w)))) {
            l -= f;
            fl += f;
            e[i].w -= f;
            e[i ^ 1].w += f;
            if (!l) break;
        }
    }
    return fl;
}
int Dinic(int s, int t) {
    int maxf = 0;
    while (bfs(s, t)) {
        maxf += dfs(s, t, INF);
    }
    return maxf;
}
void dfs(int now, int l) {
    if (vis[now]) return ;
    vis[now] = 1;
    if (wh[now] == l) {
        find[now] = 1;
    }
    for (int i = head[now]; i; i = e[i].nx) {
        if (e[i].w == l) dfs(e[i].v, l);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    r = n * m + 1;
    k = n * m + 2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char a;
            std::cin >> a;
            if (a == '.') {
                map[i][j] = 1;
                cnt++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        wb[i][1] = wb[i - 1][1] ^ 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            wb[i][j] = wb[i][j - 1] ^ 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] && wb[i][j]) {
                add(r ,g(i , j), 1);
                wh[g(i, j)] = 1;
                if (map[i + 1][j]) add(g(i, j), g(i + 1, j), 1);
                if (map[i - 1][j]) add(g(i, j), g(i - 1, j), 1);
                if (map[i][j + 1]) add(g(i, j), g(i, j + 1), 1);
                if (map[i][j - 1]) add(g(i, j), g(i, j - 1), 1);
            }
            if (map[i][j] && !wb[i][j]) {
                add(g(i, j), k, 1);
            }
        }
    }
    int tot = Dinic(r, k);
    if (cnt == tot) {
        puts("LOSE");
        return 0;
    }
    puts("WIN");
    dfs(r, 1);
    dfs(k, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (find[g(i, j)]) {
                printf("%d %d\n", i, j);
            }
        }
    }
    return 0;
}