Solution-P9169

· · 题解

本题是经典的有向图博弈问题。注意到 n,m\leq 10，所以本题三个棋子的位置 (x_1,y_1),(x_2,y_2),(x_3,y_3) 以及先后手情况的总状态数约为 2(nm)^3=2\times 10^6 级别。所以我们不妨解决一个更强的问题：对于一张有向图，初始位于状态 s，每次可以移动一步，不能移动者输，规则和原题相同，求胜负情况和对应的移动步数。

先考虑解决胜负情况的问题：

观察 1：一个状态为必胜态当且仅当其后继状态存在必败态，一个状态为必败态当且仅当其所有后继都是必胜态，否则为平局。

据此可以设计出一个基于 BFS 的算法：每次仅把非平局状态压进队列，若当前状态为必败态，则将它的所有前驱都标记为必胜态，并加入队列。若当前状态为必胜态，则检查它的某个前驱的所有后继是否全部被访问且为必胜态，若是，则把这个前驱标记为必败态，并加入队列。BFS 完成后，所有没有被访问过的结点为平局。容易得到一个 \mathcal{O}((nm)^3) 的实现。

接下来考虑操作步数的问题，观察上述 BFS 过程可以发现：

观察 2：一个状态若为必胜态，则它一定被它在队列中首次出现的后继更新步数。一个状态若为必败态，则它一定被它在队列中最后一次出现的后继更新步数。

证明很简单，因为 BFS 过程中在队列中越晚出现的结点步数越大。

回到原问题，可以发现原题已经被完全割裂成建图和 BFS 两部分，模拟即可。

下面是考场代码。笔者在考场上在 30\min 以内实现了这个思路，效率应该还是很高的。

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
#define il inline
#define re register
using namespace std;
inline int read() {
    int x = 0; bool op = false;
    char c = getchar();
    while(!isdigit(c))op |= (c == '-'), c = getchar();
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}
const int N = 15;
const int MAXN = 2e6 + 10;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
int SID, n, m, tot, etot;
char s[N][N];
int id[N][N][N][N][N][N][2];
int vis[MAXN], f[MAXN], g[MAXN], in[MAXN];
int head[MAXN], to[MAXN << 3], nxt[MAXN << 3];
void addedge(int u, int v) {to[++etot] = v; nxt[etot] = head[u]; head[u] = etot;}
il bool chk(int a, int b, int x, int y, int z, int w) {
    if(a < 1 || a > n || b < 1 || b > m)return false;
    if(x < 1 || x > n || y < 1 || y > m)return false;
    if(z < 1 || z > n || w < 1 || w > m)return false;
    if(s[a][b] == '#' || s[x][y] == '#' || s[z][w] == '#')return false;
    if(x == z && y == w)return false;
    return true;
}
int st;
il void bfs() {
    queue<int> q;
    for(re int i = 0; i < tot; i++)if(vis[i])q.push(i);
    while(q.empty() == false) {
        int u = q.front(); q.pop();
        if(u == st)return ;
        for(int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if(vis[v] == false) {
                in[v]--;
                if(g[u] == 0) {
                    g[v] = 1; f[v] = f[u] + 1;
                    vis[v] = true; q.push(v);
                }
                else if(in[v] == 0) {
                    g[v] = 0; f[v] = f[u] + 1; 
                    vis[v] = true; q.push(v);
                }
            }
        }
    }
    return ;
}
il void clr() {
    for(re int i = 0; i < tot; i++) {
        vis[i] = in[i] = f[i] = g[i] = head[i] = 0;
    }
    tot = etot = 0;
    return ;
}
il void solve() {
    queue<int> q;
    n = read(); m = read();
    for(re int i = 1; i <= n; i++)scanf("%s", s[i] + 1);
    int sa = 0, sb = 0, sx = 0, sy = 0, sz = 0, sw = 0;
    for(re int i = 1; i <= n; i++)for(re int j = 1; j <= m; j++) {
        if(s[i][j] == 'X')sa = i, sb = j;
        if(s[i][j] == 'O') {
            if(sx == 0 && sy == 0)sx = i, sy = j;
            else sz = i, sw = j;
        }
    }
    for(re int a = 1; a <= n; a++)for(re int b = 1; b <= m; b++) {
        for(re int x = 1; x <= n; x++)for(re int y = 1; y <= m; y++) {
            for(re int z = 1; z <= n; z++)for(re int w = 1; w <= m; w++) {
                if(chk(a, b, x, y, z, w) == false)continue;
                id[a][b][x][y][z][w][0] = tot++;
                id[a][b][x][y][z][w][1] = tot++;
            }
        }
    }
    st = id[sa][sb][sx][sy][sz][sw][0];
    for(re int a = 1; a <= n; a++)for(re int b = 1; b <= m; b++) {
        for(re int x = 1; x <= n; x++)for(re int y = 1; y <= m; y++) {
            for(re int z = 1; z <= n; z++)for(re int w = 1; w <= m; w++) {
                if(chk(a, b, x, y, z, w) == false)continue;
                int cur = id[a][b][x][y][z][w][0];
                for(int i = 0; i < 4; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    if(chk(a, b, nx, ny, z, w)) {
                        addedge(id[a][b][nx][ny][z][w][1], cur);
                        in[cur]++;
                    }
                    nx = z + dx[i]; ny = w + dy[i];
                    if(chk(a, b, x, y, nx, ny)) {
                        addedge(id[a][b][x][y][nx][ny][1], cur);
                        in[cur]++;
                    }
                }
                for(int i = 0; i < 3; i++) {
                    int nx = a + dx[i], ny = b + dy[i];
                    if(chk(nx, ny, x, y, z, w)) {
                        addedge(id[nx][ny][x][y][z][w][0], cur ^ 1);
                        in[cur ^ 1]++;
                    }
                }
                if(a == 1) {
                    vis[cur] = vis[cur ^ 1] = true;
                    g[cur] = 0; g[cur ^ 1] = 1;
                    f[cur] = f[cur ^ 1] = 0;
                }
                else if((a == x && b == y) || (a == z && b == w)) {
                    vis[cur] = vis[cur ^ 1] = true;
                    g[cur] = g[cur ^ 1] = 0;
                    f[cur] = f[cur ^ 1] = 0;
                }
                else {
                    if(in[cur] == 0)vis[cur] = true, g[cur] = f[cur] = 0;
                    if(in[cur ^ 1] == 0)vis[cur ^ 1] = true, g[cur ^ 1] = f[cur ^ 1] = 0;
                }
            }
        }
    }
    bfs();
    if(vis[st] == false)puts("Tie");
    else if(g[st] == 1)printf("Red %d\n", f[st]);
    else printf("Black %d\n", f[st]);
    return clr(), void();
}
int main() {
    freopen("zu.in", "r", stdin);
    freopen("zu.out", "w", stdout);
    SID = read(); int test = read();
    while(test--)solve();
    return 0;
}

但是 luogu TLE 一个点是怎么回事呢（