題解：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的基礎上增加了字母交替的約束條件，需要巧妙設計狀態來記錄連續步數。關鍵點在于：
- 正確計算下一步應該走的字母
- 合理設計狀態避免重復計算
- 處理邊界條件和終止條件
