洛谷P4055 [JSOI2009] 游戏题解

题目链接：P4055 [JSOI2009] 游戏

题意：

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

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

例如下图所示的迷宫，迷宫中 . 表示棋子可以经过的格子，而 # 表示棋子不可以经过的格子：
.##
...
#.# 
若 Alice 将棋子放置在 $(1,1)$，则 Alice 则无论如何都无法赢得游戏。

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

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

输入格式：

输入数据首先输入两个整数 $N,M$，表示了迷宫的边长。

接下来 $N$ 行，每行 $M$ 个字符，描述了迷宫。

输出格式：

若 Alice 能够赢得游戏，则输出一行 WIN

然后输出所有可以赢得游戏的起始位置，按行优先顺序输出，每行一个。

否则输出一行 LOSE。

数据范围：

$1 \leq n,m \leq 100$。

经典的二分图博弈。

考虑对整个棋盘黑白染色，即 $x+y$ 相同的染同一种颜色。

方便起见，考虑整张图连通（即只有一个连通块）的情况。

我们将每个点向周围四个点连双向边（障碍物除外），那么显然构建出的图构成一个二分图

可以证明，先手必败当且仅当这个二分图存在完美匹配，否则先手必胜。

原因很简单，因为存在完美匹配时，先手随便选哪个，后手都有匹配的点可以选，所以先手必败。

那么如何找到所有必胜的起点呢？由于必胜情况下不存在完美匹配，所以我们可以求出一个最大匹配

对于一侧没有匹配到的点 $i$ ，我们找与它相连的（显然在另一侧）且已经匹配成功的点 $j$ 。

假设 $j$ 匹配了 $k$ ，那么先手选 $k$ ，后手选 $j$ ，先手再选 $i$ 就赢了，由此可知 $i,k$ 均为先手必胜的起点。

以上思路适用于一个连通块的情况。那么多个连通块的情况也是一样的，我们对于每个连通块都跑一遍就好了

注意建图的时候要记录连通块里的点，不要暴力扫整个棋盘，否则复杂度直接起飞。

时间复杂度 $\mathcal{O}(n^2)$ ，这道题用匈牙利算法会方便一些。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(111))
#define Fi first
#define Se second

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
char s[N][N], ans[N * N]; pii stk[N * N];
int n, m, tim, pos = 1, top, vis[N * N], col[N][N], head[N * N], npy[N * N];
struct Edge { int v, next; } e[4 * N * N];
void addEdge(int u, int v) { e[++pos] = {v, head[u]}; head[u] = pos; }
int id(int x, int y) { return (x - 1) * m + y; }
void build(int x, int y)
{
    stk[++top] = pii(x, y); col[x][y] = tim;
    rep(i, 0, 3)
    {
        const int tx = x + dx[i], ty = y + dy[i];
        if(tx < 1 || ty < 1 || tx > n || ty > m || s[tx][ty] == '#') continue;
        addEdge(id(x, y), id(tx, ty)); if(!col[tx][ty]) build(tx, ty);
    }
}
bool dfs(int u, int now)
{
    if(vis[u] == now) return false;
    vis[u] = now;
    for(int i = head[u]; i; i = e[i].next)
    {
        const int v = e[i].v;
        if(!npy[v] || dfs(npy[v], now)) { npy[v] = u; npy[u] = v; return true; }
    }
    return false;
}
void dfs2(int u)
{
    if(ans[u]) return; ans[u] = true;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(npy[v]) dfs2(npy[v]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; rep(i, 1, n) cin >> (s[i] + 1);
    bool ok = false;
    rep(i, 1, n) rep(j, 1, m) if(!col[i][j] && s[i][j] == '.')
    {
        while(top)
        {
            const auto u = stk[top]; --top;
            head[id(u.Fi, u.Se)] = npy[id(u.Fi, u.Se)] = 0;
        }
        pos = 0; ++tim; build(i, j);
        rep(k, 1, top)
        {
            const auto u = stk[k]; static int now = 0;
            if((u.Fi + u.Se) & 1) dfs(id(u.Fi, u.Se), ++now);
        }
        bool ck = false;
        rep(k, 1, top)
        {
            const auto u = stk[k];
            if(!npy[id(u.Fi, u.Se)]) { ck = true; dfs2(id(u.Fi, u.Se)); }
        }
        ok |= ck;
    }
    if(!ok) return cout << "LOSE\n", 0;
    cout << "WIN\n";
    rep(i, 1, n) rep(j, 1, m) if(ans[id(i, j)]) cout << i << ' ' << j << '\n';
    return 0;
}