题解：P9425 [蓝桥杯 2023 国 B] AB 路线
题目传送门
P9425 [蓝桥杯 2023 国 B] AB 路线
一、题目描述
给定一个N×M的迷宫，每个格子标记为A或B。从左上角(1,1)出发，需要移动到右下角(N,M)。移动规则是：必须交替走K个A格子和K个B格子，最后一段可以不足K个。求最少步数，若无法到达则输出-1。
二、题目分析
这是一个典型的带约束的最短路径问题，需要在普通BFS的基础上增加对移动规则的检查。关键在于如何记录当前已经连续走了多少个相同字母的格子。
三、解题思路
- 使用BFS进行最短路径搜索
- 状态需要记录：当前位置(x,y)、当前步数sum、当前连续走的相同字母数量
- 每次移动时检查：
- 下一个格子的字母是否符合交替规则
- 连续相同字母数量是否超过K
- 使用三维数组st[x][y][cnt]记录是否访问过某个状态，避免重复计算
四、算法讲解（结合例子）
以样例为例：
4 4 2
AAAB
ABAB
BBAB
BAAA
- 起点(1,1)是A，初始状态(1,1,0)
- 第一步可以走A（连续1个A），状态变为(2,1,1)
- 第二步必须走A（因为K=2），状态变为(3,1,0)（因为已经连续2个A，下次需要B）
- 第三步必须走B，状态变为(3,2,1)
- …直到到达终点(4,4)
五、代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, k;
char g[N][N];
struct Node {int x, y, sum = 0;char ch;Node() : x(0), y(0), sum(0), ch('\0') {}Node(int _x, int _y, int _sum, char _ch) : x(_x), y(_y), sum(_sum), ch(_ch) {}
};Node q[N * N * 10]; // 队列
bool st[N][N][15]; // 状态标记数组，第三维记录连续步数int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};void bfs() {int tt = -1, hh = 0;q[++tt] = {1, 1, 0, 'A'}; // 起点st[1][1][0] = true;while (hh <= tt) {auto t = q[hh++];if (t.x == n && t.y == m) { // 到达终点cout << t.sum;return;}for (int i = 0; i < 4; i++) {int a = t.x + dx[i];int b = t.y + dy[i];if (a < 1 || b < 1 || a > n || b > m) continue; // 边界检查// 计算下一个应该走的字符int tmp = ((t.sum + 1) / k) % 2;char nextch = 'A' + tmp;if (st[a][b][(t.sum % k) + 1]) continue; // 状态已访问if (g[a][b] == nextch) { // 字母符合要求st[a][b][(t.sum % k) + 1] = true;q[++tt] = {a, b, t.sum + 1, g[a][b]};}}}cout << -1; // 无法到达
}void solve() {cin >> n >> m >> k;for (int i = 1; i <= n; i++)cin >> (g[i] + 1); bfs();
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}
六、重点细节
- 状态设计：使用三维状态(x,y,cnt)，其中cnt记录当前连续走的相同字母数量
- 字母交替规则：通过
((sum+1)/k)%2计算下一步应该走A还是B - 边界处理：检查坐标是否越界
- 状态去重：使用st数组避免重复访问相同状态
七、复杂度分析
- 时间复杂度：O(NMK)，每个格子最多被访问K次
- 空间复杂度：O(NMK)，用于存储状态标记
八、总结
本题在传统BFS的基础上增加了字母交替的约束条件，需要巧妙设计状态来记录连续步数。关键点在于：
- 正确计算下一步应该走的字母
- 合理设计状态避免重复计算
- 处理边界条件和终止条件