题目地址：洛谷：【P4055】[JSOI2009]游戏 – 洛谷、BZOJ：Problem 1443. — [JSOI2009]游戏Game

题目描述

小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 \times m$矩形地图，有的格子不能走，每次选择一个起点，然后两个玩家轮流将放在起点的棋子移动一步，只能经过同一个格子一次，最后不能移动的玩家输，求是否后手必胜。

输入输出格式

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

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

输入输出样例

输入样例#1：

3 3
.##
...
#.#

输出样例#1：

WIN
2 3
3 2

说明

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

题解

首先对矩形黑白染色，连边成为二分图，我们发现，可以利用匈牙利算法中的交错路来解决这个问题。首先跑一遍最大匹配。
如果为完美匹配的状况，当选择任何一个匹配点为出发点，则先手一定每次走一条匹配边，而最后一条边也是匹配边，先手必胜。
否则，先手从非匹配点出发，无论如何都会走到一个匹配点上，此时，后手会经历类似上面的情况，后手必胜。由于还要输出方案，我们还要找最大匹配时一定不是匹配点的点，可以从非匹配点出发寻找交错路，与非匹配点在二分图中同边的点都是答案。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 10005;
const int fix[][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};

int n, m;

std::vector<int> gra[MAXN];

int match[MAXN], vis[MAXN], clk;

bool dfs(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] != clk) {
            vis[v] = clk;
            if(!match[v] || dfs(match[v])) {
                match[v] = u; match[u] = v; return true;
            }
        }
    }
    return false;
}

inline int bmatch() {
    int res = 0;
    for(int i = 1; i <= n * m; i++) {
        if(!match[i]) {
            clk++; if(dfs(i)) res++;
        }
    }
    return res;
}

bool ans[MAXN];

void dfs_ans(int u) {
    if(ans[u]) return;
    ans[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(match[v]) dfs_ans(match[v]);
    }
}

inline int id(int x, int y) {
    return (x - 1) * m + y;
}

inline int col(int x, int y) {
    return (x + y) & 1;
}

char mmp[105][105];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            mmp[i][j] = readsingle();
        }
    }
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mmp[i][j] == '#') continue;
            tot++;
            if(col(i, j)) continue;
            for(int k = 0; k < 4; k++) {
                int nx = i + fix[0][k], ny = j + fix[1][k];
                if(nx < 1 || nx > n || ny < 1 || ny > m || mmp[nx][ny] == '#') continue;
                gra[id(i, j)].push_back(id(nx, ny));
                gra[id(nx, ny)].push_back(id(i, j));
            }
        }
    }
    if(bmatch() * 2 == tot) {
        puts("LOSE"); return 0;
    }
    puts("WIN");
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!match[id(i, j)]) {
                dfs_ans(id(i, j));
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mmp[i][j] != '#' && ans[id(i, j)]) {
                printf("%d %d\n", i, j);
            }
        }
    }
    return 0;
}