自动搬运

查看原文

来自洛谷，原作者为

	LPF 看不懂黑白却听得到钟摆，去新世界冒险和内心作伴

搬运于2025-08-24 22:02:22，当前版本为作者最后更新于2022-06-07 17:29:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大概是全网找不到什么题解所以写一发，顺便求个卡常大师卡卡常。

[BalticOI 2008]游戏

给定 $n\times n$ 的矩阵，有 A 和 B 两人的起点和障碍物。

由 A 先走，每次每人轮流走一步，如果走到另一个人头上就必须再走一步。

谁先到达另一个人的起点谁获胜，如果到达对方起点时对方恰好在自己起点上，也视为获胜。

不难发现先手具有巨大优势，因为两人的最短路径长度（设为 $D$）是一样的，唯一的翻盘点在 B 跳到 A 头上一次。

性质一：每个人必走最短路径。

否则另一个人只要坚定的走最短路径就必然获胜。

这样预处理从 A,B 两点出发，到每个格子的最短距离，称 $\text{dis}_{A}=D-\text{dis}_{B}$ 的格子为合法格子。

性质二：若 $D$ 为奇数则 A 必胜。

这个也显然，因为这样 B 想碰到 A 也碰不上。

同时发现，偶数时，如果 B 碰上了 A，一定是两者同时到达 $\text{dis}_A=\text{dis}_B=\dfrac{D}{2}$ 的格子，称这样的格子为关键格子。

基于这些性质，就很容易想到做法。

设 $S(x,y)$ 表示从 $(x,y)$ 出发，只通过 合法格子 能到达的 关键格子 集合。

性质三：B 能获胜当且仅当：

对于 A 的每条从起点到某个 关键格子 路径：$(ax_0,ay_0),(ax_1,ay_1),\cdots,(ax_{\frac{D}{2}},ay_{\frac{D}{2}})$。（其中 $0$ 下标表示对应人的起点）

都有至少一条 B 的路径：$(bx_0,by_0),(bx_1,by_1),\cdots,(bx_{\frac{D}{2}},by_{\frac{D}{2}})$，满足 $\forall i\in[0,\frac{D}{2}],S(ax_i,ay_i)\subset S(bx_i,by_i)$。

相当于，对于每次 A 的移动，B 总能合理的移动，使得 A 能到的关键格子 B 都能到。这样显然 B 能碰上 A，否则不能。

具体实现上，只需要对于每个同层的 A,B 路径中的格子对枚举判断。

如果对于 A 格子的下一步的每个格子，都有至少一个 B 的下一步能到的格子与之匹配，那么它们匹配。

最终只要验证 A,B 的起点是否匹配即可。

因为每层的格子数是 $O(n)$ 的，所以总复杂度是 $O(Tn^3)$ 的，在 loj 上通过了，但在洛谷上还是 t 了两个点。

在线求卡常大师/kel

#include<bits/stdc++.h>
typedef long long LL;
#define rep(i, a, b) for(register int i = (a); i <= (b); i ++)
#define per(i, a, b) for(register int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second

const int N = 310;
int n, dis[2][N][N], flg[N][N], num[N][N];
char str[N][N];
vector<pii> vec[N * N];
bool vis[2][N << 1][N << 1];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

inline void clear() {memset(vis, false, sizeof(vis)); rep(i, 0, n << 1) vec[i].clear();}

inline int get(pii cur) {return num[cur.fi][cur.se];}

inline void calc(int sx, int sy, int o) {
	rep(i, 1, n) rep(j, 1, n) dis[o][i][j] = -1;
	dis[o][sx][sy] = 0;
	queue<pii> q; q.push(mp(sx, sy));
	while(! q.empty()) {
		pii u = q.front(); q.pop();
		int x = u.fi, y = u.se;
		rep(d, 0, 3) {
			int nx = x + dx[d], ny = y + dy[d];
			if(nx < 1 || nx > n || ny < 1 || ny > n || str[nx][ny] == '#' || dis[o][nx][ny] != -1) continue;
			dis[o][nx][ny] = dis[o][x][y] + 1;
			q.push(mp(nx, ny));
		}
	}
}

inline vector<pii> solve(pii cur, int o) {
	int x = cur.fi, y = cur.se;
	vector<pii> now;
	rep(d, 0, 3) {
		int nx = x + dx[d], ny = y + dy[d];
		if(nx < 1 || nx > n || ny < 1 || ny > n || str[nx][ny] == '#') continue;
		if(flg[nx][ny] == flg[x][y] + o) now.push_back(mp(nx, ny));
	}
	return now;
}

inline bool involve(pii a, vector<pii> bcur) {
	for(pii b : bcur) if(vis[0][get(a)][get(b)]) return true;
	return false;
}

int ax, ay, bx, by;

void work() {
	n = read(), clear();
	rep(i, 1, n) scanf("%s", str[i] + 1);
	rep(i, 1, n) rep(j, 1, n)
		if(str[i][j] == 'A') ax = i, ay = j;
		else if(str[i][j] == 'B') bx = i, by = j;
	calc(ax, ay, 0);
	calc(bx, by, 1);
	int Dis = dis[0][bx][by];
	if(Dis & 1) {puts("A"); return;}
	rep(i, 1, n) rep(j, 1, n) {
		flg[i][j] = -1;
		if(dis[0][i][j] != -1 && dis[1][i][j] != -1 && Dis - dis[0][i][j] == dis[1][i][j]) {
			flg[i][j] = dis[0][i][j], vec[flg[i][j]].push_back(mp(i, j));
			num[i][j] = vec[flg[i][j]].size();
		}
	}
	rep(i, 1, (int) vec[Dis / 2].size()) vis[0][i][i] = true;

	per(d, Dis / 2 - 1, 0) {
		for(pii a : vec[d]) {
			vector<pii> acur = solve(a, 1);
			for(pii b : vec[Dis - d]) {
				vector<pii> bcur = solve(b, - 1);
				bool flag = true;
				for(pii o : acur) if(! involve(o, bcur)) {flag = false; break;}
				if(flag) vis[1][get(a)][get(b)] = true;
			}
		}
		rep(i, 1, (int) vec[d + 1].size()) rep(j, 1, (int) vec[Dis - d - 1].size()) vis[0][i][j] = false;
		rep(i, 1, (int) vec[d].size()) rep(j, 1, (int) vec[Dis - d].size()) vis[0][i][j] = vis[1][i][j], vis[1][i][j] = false;
	}
	puts(vis[0][get(mp(ax, ay))][get(mp(bx, by))] ? "B" : "A");
}

int main() {
	int t = read();
	while(t --) work();
	return 0;
}