题解

该题是 Baltic OI 2008《Game》：两人轮流在棋盘上移动，目标是最先到达对方起点。解法分两步：

1. 最短路预处理：从 A、B 各做一次 BFS，得到每个白格到 A、B 的最短距离 dist[0]、dist[1]，并记最短对抗路径长度 d。若 d 为奇数，则先手 A 一定能抢先一步走到对方家，直接输出 A。
2. 沿最短路径做博弈 DP：只需要考虑所有位于某条最短路上的格子，即满足 dist[0][x][y] + dist[1][x][y] == d 的点。把这些点按离 A 的距离（以及对称的离 B 的距离）分层存入 p1、p2。
   • 以中间层（距离为 d/2）为初态，两个玩家都在这个层的同一个格子时认为 B 已经守住（dp[cur][i][i]=1）。
   • 从中间层向前倒推，对于 p1 层里的每个格子（A 的可能位置），枚举它的所有“合法前驱”——即下一步能够沿最短路前进的邻格。B 需要找到一个对应的邻格，使得状态仍然保持可赢；如果有某个 A 的前驱无法找到匹配，说明 B 必败。
   • 若初态 dp[0][0][0] 为真，说明 B 可以一路镜像 A 的走法并最终获胜；否则 A 获胜。

整个过程每个格子最多处理常数次，复杂度 $(O(n^2))$。

#include<bits/stdc++.h>
using namespace std;
const int N = 300;
const int M = 9e4;
const int mod = 10000;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int T, n;
char ch[N + 5][N + 5];
int dist[2][N + 5][N + 5];
bool dp[2][(N << 1) + 5][(N << 1) + 5];
int idx[N + 5][N + 5];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
vector<pair<int, int> > p1[M + 5], p2[M + 5]; 

void init() {
	memset(dist, 0x3f, sizeof dist);
	memset(idx, 0, sizeof idx);
	memset(idx, -1, sizeof idx);
	for (int i = 0; i <= n * n; i++) {
		p1[i].clear();
		p2[i].clear();
	}
	memset(dp, 0, sizeof dp);
}

queue<pair<int, int> > que;
int bfs(int idx) {
	int stx = 1, sty = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (ch[i][j] == 'A' + idx) {
				stx = i;
				sty = j;
			}
		}
	}
	dist[idx][stx][sty] = 0;
	que.push(make_pair(stx, sty));
	int res = 0;
	while (!que.empty()) {
		auto cur = que.front();
		que.pop();
		if (ch[cur.first][cur.second] == 'B' && idx == 0) {
			res = dist[0][cur.first][cur.second];
		}
		for (int i = 0; i < 4; i++) {
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];
			if (!(x >= 1 && x <= n && y >= 1 && y <= n) || ch[x][y] == '#') {
				continue;
			}
			if (dist[idx][x][y] != INF) {
				continue;
			}
			dist[idx][x][y] = dist[idx][cur.first][cur.second] + 1;
			que.push(make_pair(x, y));
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n;
		init();
		for (int i = 1; i <= n; i++) {
			cin >> (ch[i] + 1);
		}
		int d = bfs(0);
		bfs(1);
		if (d & 1) {
			cout << "A\n";
			continue;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[0][i][j] + dist[1][i][j] == d) {
					if (dist[0][i][j] <= d / 2) {
						p1[dist[0][i][j]].push_back(make_pair(i, j));
						idx[i][j] = p1[dist[0][i][j]].size() - 1;
					}
					if (dist[0][i][j] >= d / 2) {
						p2[d - dist[0][i][j]].push_back(make_pair(i, j));
						idx[i][j] = p2[d - dist[0][i][j]].size() - 1;
					}
				}
			}
		}
		for (int i = 0; i < p1[d / 2].size(); i++) {
			dp[0][i][i] = 1;
			//cout << p1[d / 2][i].first << " " << p1[d / 2][i].second << "\n";
		}
//		for (int i = 1; i <= n; i++) {
//			for (int j = 1; j <= n; j++) {
//				cout << idx[i][j] << " ";
//			}
//			cout << "\n";
//		}
		int cur = 0, nxt = 1;
		for (int i = d / 2 - 1; i >= 0; i--) {
			int sz1 = p1[i].size(), sz2 = p2[i].size();
			p1[i + 1].clear();
			p2[i + 1].clear();
			for (int j = 0; j < sz1; j++) {
				for (int k = 0; k < sz2; k++) {
					dp[nxt][j][k] = 1;
					for (int h1 = 0; h1 < 4; h1++) {
						int x1 = p1[i][j].first + dx[h1];
						int y1 = p1[i][j].second + dy[h1];
						if (!(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n) || ch[x1][y1] == '#') {
							continue;
						}
						if (dist[0][x1][y1] != dist[0][p1[i][j].first][p1[i][j].second] + 1 || dist[0][x1][y1] + dist[1][x1][y1] != d) {
							continue;
						}
						int f = 0;
						for (int h2 = 0; h2 < 4; h2++) {
							int x2 = p2[i][k].first + dx[h2];
							int y2 = p2[i][k].second + dy[h2];
							if (!(x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= n) || ch[x2][y2] == '#') {
								continue;
							}
							if (dist[1][x2][y2] != dist[1][p2[i][k].first][p2[i][k].second] + 1 || dist[0][x2][y2] + dist[1][x2][y2] != d) {
								continue;
							}
							int idx1 = idx[x1][y1], idx2 = idx[x2][y2];
							if (dp[cur][idx1][idx2]) {
								f = 1;
								break;
							}
						}
						if (!f) {
							dp[nxt][j][k] = 0;
							break;
						}
					}
					//cout << i << " " << p1[i][j].first << " " << p1[i][j].second << " " << p2[i][k].first << " " << p2[i][k].second << " " << dp[nxt][j][k] << "\n";
				}
			}
			swap(cur, nxt);
		}
		cout << (dp[cur][0][0] ? "B" : "A") << "\n";
	}
	return 0;
}