【题解】BZOJ 1443 [JSOI2009]游戏

请注意,本文编写于 146 天前,最后修改于 145 天前,其中某些信息可能已经过时。

Problem

在 $N\times M$ 的迷宫中有一个棋子,$AA$ 首先任意选择棋子放置的位置。然后 $YY$ 和 $AA$ 轮流将棋子移动到相邻的格子里

游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏

求 $AA$ 初始将棋子放在哪些格子会有必胜策略

Thought

按照套路将棋盘二染色

如果跑出最大匹配后,从某个非匹配点开始的状态,先手必然只能走到匹配点,此点必然有一条匹配边,后手走这条匹配边

对先手的任意操作,是通过一条非匹配边走向一个未走过的匹配点
对后手的任意操作,是通过一条匹配边走向一个匹配点

显然,每个匹配点必然有且仅有一条匹配边,走到任意一个匹配点时,后手都会走到其对应的另外一个匹配点,无论如何,后手都有路可走
所以,后手必胜

同样,如果从一个匹配点开始,先手必胜

一般来说,可以从左侧某个未匹配点开始,进行 DFS ,其能够遇到的所有左侧的点都能够被其替代

右侧同理

所以这次要将所有边建出来,两边都要搜

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
struct Edge {
    int t, n;
};
Edge e[N * N << 2];
int head[N * N], tot;
int match[N * N];
int tim[N * N], times;
bool vis[N * N];
int win;
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
bool check(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && s[i][j] != '#';
}
bool dfs(int x) {
    for(int i = head[x]; i; i = e[i].n) {
        if(tim[e[i].t] == times) continue;
        tim[e[i].t] = times;
        if(match[e[i].t] == - 1 || dfs(match[e[i].t])) {
            match[e[i].t] = x;
            match[x] = e[i].t;
            return true;
        }
    }
    return false;
}
void find(int x) {
    vis[x] = 1; ++ win;
    for(int i = head[x]; i; i = e[i].n)
        if(!vis[match[e[i].t]])
            find(match[e[i].t]);
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++ i)
        scanf("%s", s[i]);
    for(int i = 0; i < n; ++ i)
        for(int j = 0 ; j < m; ++ j) {
            if(s[i][j] == '#') continue;
            if(check(i , j - 1)) addedge(i * m + j, i * m + j - 1);
            if(check(i , j + 1)) addedge(i * m + j, i * m + j + 1);
            if(check(i - 1 , j)) addedge(i * m + j, i * m + j - m);
            if(check(i + 1 , j)) addedge(i * m + j, i * m + j + m);
        }
    memset(tim, - 1, sizeof(tim));
    memset(match, - 1, sizeof(match));
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if((i + j) % 2 == 0 && s[i][j] != '#') {
                times = i * m + j;
                dfs(i * m + j);
            }
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(match[i * m + j] == - 1 && s[i][j] != '#')
                find(i * m + j);
    if(!win) puts("LOSE");
    else {
        puts("WIN");
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < m; ++ j)
                if(vis[i * m + j] && s[i][j] != '#')
                    printf("%d %d\n", i + 1, j + 1);
    }
    return 0;
}
Comments

添加新评论