自动搬运

查看原文

来自洛谷，原作者为

	ChampionCyan Cyan你又压！

搬运于2025-08-24 22:59:02，当前版本为作者最后更新于2024-07-04 18:54:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}