题解：P10543 [THUPC2024] 黑白

· · 题解

P10543题解

首先判定是否有路径从 (1,1) 到 (n,m)，若没有，后手必胜。

否则计算有几个选择后仍有路径的点（两个人一共还能选几个点），若数量为奇数则先手胜，否则后手胜。

随后我们发现最初可能有不止一条路径，他们可能长短不同！

没关系，请看：

\square\blacksquare\square\blacksquare\square\blacksquare \blacksquare\square\blacksquare\square\blacksquare\square \square\blacksquare\square\blacksquare\square\blacksquare \blacksquare\square\blacksquare\square\blacksquare\square \square\blacksquare\square\blacksquare\square\blacksquare \blacksquare\square\blacksquare\square\blacksquare\square

可以通过染色法得出图中：

标记（或者说颜色）相同的两个点无论怎样“绕路”，最终距离一定为偶数。

标记（或者说颜色）不同的两个点无论怎样“绕路”，最终距离一定为奇数。

因此最终路径长度的奇偶性一定不会发生改变，为了方便，我们直接 BFS 求最短路长度的奇偶性就能得出答案。

code（马蜂自认为好看）：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
const int inf = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

inline int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ret = (ret << 1) + (ret << 3) + ch - '0';
        ch = getchar();
    }
    return ret * f;
}

int n, m, dis[MAXN][MAXN];
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
queue<pair<int, int> > q;

inline bool bfs() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dis[i][j] = inf, vis[i][j] = s[i][j] == 'B';
    if (vis[1][1])
        return false;
    dis[1][1] = 1, q.push(make_pair(1, 1));
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m || vis[nx][ny])
                continue;
            q.push(make_pair(nx, ny)), dis[nx][ny] = dis[x][y] + 1, vis[nx][ny] = true;
        }
    }
    return dis[n][m] != inf;
}

int main() {
    int t = read();
    while (t--) {
        n = read(), m = read();
        int w = 0;
        for (int i = 1; i <= n; i++)
            scanf("%s", s[i] + 1);
        if (!bfs()) {
            puts("J");
            continue;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s[i][j] == 'W')
                    w++;
        if ((w - dis[n][m]) & 1)
            puts("I");
        else
            puts("J");
    }
    return 0;
}