2 条题解

  • 0
    @ 2025-10-22 16:16:26

    题解

    思路分析

    这是一道经典的博弈论 + BFS + 动态规划问题，需要判断双人对抗游戏的必胜策略。

    问题建模

    • 两个玩家 A 和 B 在 n×nn \times n 的棋盘上博弈
    • A 先手，双方轮流移动自己的棋子到相邻白色格子
    • 如果移动到对方位置，可以再移动一步（越过对手）
    • 先到达对方起点的玩家获胜

    核心思路

    1. 状态定义

    状态 (x1,y1,x2,y2,turn)(x_1, y_1, x_2, y_2, turn) 表示：

    • A 在 (x1,y1)(x_1, y_1)，B 在 (x2,y2)(x_2, y_2)
    • turn 表示当前轮到谁

    但这样状态数过大。优化方法：

    关键观察：两个玩家沿着最短路同时向对方起点移动，判断谁能先到达。

    2. BFS预处理

    对 A 和 B 的起点分别做 BFS，预处理：

    • dist[0][i][j]dist[0][i][j]：A 起点到 (i,j)(i,j) 的最短距离
    • dist[1][i][j]dist[1][i][j]：B 起点到 (i,j)(i,j) 的最短距离

    3. 奇偶性剪枝

    如果从 A 到 B 的最短路长度 dd 为奇数，则 A 必胜（因为 A 先手，走 dd 步到达）。

    4. 博弈DP（偶数距离情况）

    当 dd 为偶数时，需要判断精确博弈胜负。

    定义 dp[cur][i1][i2]dp[cur][i_1][i_2] 表示：

    • 第 cur 层（距离起点的步数）
    • A 在第 i1i_1 个候选位置，B 在第 i2i_2 个候选位置
    • 当前状态下 A 是否有必胜策略

    关键：只考虑在最短路上的格子（满足 dist[0][i][j]+dist[1][i][j]=ddist[0][i][j] + dist[1][i][j] = d）。

    状态转移：

    • 枚举 A 的下一步所有可能位置
    • 对于 A 的每一步，枚举 B 的所有可能应对
    • A 有必胜策略 ⇔\Leftrightarrow 存在一步使得无论 B 如何应对都输

    算法步骤

    1. BFS预处理：

      • 从 A 起点 BFS，得到 dist[0]dist[0]
      • 从 B 起点 BFS，得到 dist[1]dist[1]
      • 计算最短路长度 dd

    2. 奇偶性判断：

      • 如果 dd 为奇数，输出 "A"

    3. 收集最短路上的点：

      • 找到所有满足 dist[0][i][j]+dist[1][i][j]=ddist[0][i][j] + dist[1][i][j] = d 的格子
      • 按距离 A 起点的距离分层存储

    4. 博弈DP：

      • 从中点向两端倒推
      • 判断初始状态（A 和 B 在起点）的胜负

    复杂度分析

    • BFS：O(n2)O(n^2)
    • DP：O(d⋅p2⋅4)O(d \cdot p^2 \cdot 4)，其中 pp 是每层的点数
    • 总时间复杂度：O(n2+d⋅p2)O(n^2 + d \cdot p^2)
    • 空间复杂度：O(n2)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;
}
    • 0
      @ 2025-10-17 18:33:23

      题解

      该题是 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;
}
      • 1

      「BalticOI 2008」游戏

      信息

      ID
      3239
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      递交数
      1
      已通过
      1
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 黔ICP备2023002402号-2
      3. Worker 0, 41ms
      4. Powered by Hydro v4.19.1 Community, Modified by 33DAI