题解 BFS + 分层图 - 学习分层图: [[蓝桥杯]真题讲解：AB路线（BFS+分层图）](https://www.bilibili.com/video/BV11f42127Lf/) 为什么有 $k$ 层? - 先看 $vis[i][j][k]$ 的定义: 小人走到 $[i][j]$ 格子, 并且是还需要走 $k$ 个格子才可以 换格子种类. (从这个定义也可以看出来, 为什么vis[ny][nx][dk] = true这样更新(即 为什么是更新相邻的 (dk 和 dk - 1)), 因为走格子就是按顺序的嘛) ```C++ #include <cstdio> #include <functional> #include <vector> #include <queue> #include <tuple> using namespace std; const int fx[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); vector<vector<char>> tiz(n, vector<char>(m)); // 分层图, 标记 vis[i][j][k] 为已走过的 vector<vector<vector<char>>> vis(n, vector<vector<char>>(m, vector<char>(k))); // The vis[i][j][k] for (int i = 0; i < n; ++i) { char str[m + 1]; scanf("%s", str); for (int j = 0; j < m; ++j) { tiz[i][j] = str[j]; } } // bfs vis[0][0][k - 1] = 1; // 还不知道为什么不写也可以过 // 队列元组: 上一次访问的 [y][x], 已经走了 dk 个 A或B, 总路程 mo queue<tuple<int, int, int, int>> pq; pq.push(make_tuple(0, 0, k, 0)); while (pq.size()) { int i, j, dk, mo; tie(i, j, dk, mo) = pq.front(); pq.pop(); if (i == n - 1 && j == m - 1) { // 结束(最先到达必定是最小的) printf("%d\n", mo); return 0; } --dk, ++mo; for (int z = 0; z < 4; ++z) { int ny = i + fx[z][0], nx = j + fx[z][1]; if (ny < 0 || nx < 0 || ny >= n || nx >= m || vis[ny][nx][dk]) continue; // 判断 是接着走 A/B 还是换着走 (通过 dk 是否为 0 判断) // tiz 是 图, 判断当前走的是否符合和上一次走的 if (dk && tiz[i][j] == tiz[ny][nx]) { vis[ny][nx][dk] = true; pq.push(make_tuple(ny, nx, dk, mo)); } else if (!dk && tiz[i][j] != tiz[ny][nx]) { vis[ny][nx][dk] = true; pq.push(make_tuple(ny, nx, k, mo)); } } } printf("-1\n"); // 没有路径 return 0; } ```