蓝桥杯真题解析：三维BFS解决大胖子走迷宫问题

1. 项目概述当“大胖子”遇上迷宫看到“大胖子走迷宫”这个题目很多参加过蓝桥杯国赛的朋友估计都会心一笑或者眉头一紧。这道来自第十届蓝桥杯国赛的真题可以说是BFS广度优先搜索算法的一道经典“变种题”和“拔高题”。它不像基础的迷宫问题那样仅仅让你找一条从起点到终点的最短路径而是引入了一个非常有趣且棘手的设定角色是一个会“膨胀”和“收缩”的胖子。这个设定瞬间将问题复杂度提升了一个维度也完美考察了选手对BFS核心思想的理解深度、状态建模能力以及代码实现的严谨性。简单来说题目描述了一个n x n的网格迷宫其中有障碍物‘#’和可通行的空地‘*’。我们的主角“大胖子”初始时占据5x5的格子即其中心点加上上下左右各两格的范围他每移动一步需要1单位时间。但关键在于随着时间的推移他的体型会发生变化在初始的0时刻他是5x5的“大胖子”经过k个单位时间后他会收缩成3x3的“中胖子”再经过k个单位时间最终会变成1x1的“小胖子”即只占据一个格子。体型的变化直接影响了他能否通过狭窄的通道。例如一个1x1的格子小胖子能过但大胖子就过不去因为他的“身体”会撞到墙。这就要求我们在进行路径搜索时不能只记录坐标(x, y)还必须记录当前的时间t因为时间决定了胖子当前的体型进而决定了在某个时间点站在某个位置是否合法。这题的核心魅力在于它打破了传统BFS中“状态即坐标”的思维定式引入了“时间”作为状态的第三个维度。你不仅要搜索空间还要在时间维度上规划“等待”。有时候最快到达终点的策略可能不是一直向前冲而是在某个路口“等一等”等自己瘦下来之后再通过狭窄区域。这种“以时间换空间”的策略正是本题的解题精髓也是区分普通选手和高手的关键。接下来我就结合自己多次模拟和教学的经验把这题的“里里外外”拆解清楚从思路分析到代码实现再到各种坑点一次性讲透。2. 核心思路与状态建模为什么是三维BFS面对这道题第一个要突破的思维关卡就是状态到底是什么如果你只把(x, y)坐标当作状态用标准的二维BFS去写很快就会发现问题。假设胖子在t0时刻位于起点体型是5x5。他前方有一个宽度为1的走廊左右都是墙小胖子能过大胖子不能过。按照二维BFS他会尝试向走廊移动程序检查发现他5x5的身体会撞墙于是这个移动被判定为非法路径搜索在此中断。但实际上他完全可以在起点等待一段时间等体型变成3x3甚至1x1后再顺利通过走廊。所以“时间”成为了影响决策的关键变量。在t时刻胖子的体型是确定的。因此一个完整的状态应该由三元组(x, y, t)构成。其中(x, y)是胖子中心点所在的坐标t是当前时刻。有了这个三维状态BFS队列中存储的就不再是简单的坐标而是(x, y, t)。每次从队列中取出一个状态我们考虑从这个状态出发下一步可以做什么。注意这里有一个非常重要的细节也是很多初学者容易混淆的“移动”和“等待”是两种不同的操作。移动操作从当前状态(x, y, t)尝试向上下左右四个方向移动一格。移动后中心点坐标变为(nx, ny)时间变为t1。然后你需要判断在t1这个时刻胖子以他t1时刻对应的体型中心点站在(nx, ny)位置其身体所覆盖的所有格子是否都在迷宫范围内且都不是障碍物‘#’。如果全部满足则新状态(nx, ny, t1)是合法的可以入队。等待操作胖子也可以选择原地不动等待1单位时间。这会产生一个新状态(x, y, t1)。同样需要检查在t1时刻胖子以t1时刻的体型站在(x, y)位置是否合法。这通常是合法的因为原地不动一般不会撞墙但严谨起见仍需判断。通过将“等待”也视为一种合法的状态转移BFS算法就能自动探索出“在某个点等待瘦身”的最优策略。因为BFS是按“层次”即时间t逐层扩展的它第一次搜索到终点状态(ex, ey, t)时这个t就是最短时间。2.1 体型判断函数的实现细节这是整个算法的核心函数决定了状态是否合法。它的作用是给定时间t和中心坐标(cx, cy)判断胖子当前的身体是否完全在空地内。首先需要根据时间t计算出胖子当前的体型半径r。题目设定通常是当0 t k时r 2(占据5x5格子即上下左右各2格)当k t 2*k时r 1(占据3x3格子即上下左右各1格)当t 2*k时r 0(占据1x1格子即只占中心点)那么判断函数check(cx, cy, t)的逻辑如下根据t计算出半径r。遍历一个正方形区域其左上角为(cx-r, cy-r)右下角为(cxr, cyr)。对于这个区域内的每一个格子(i, j)首先判断(i, j)是否在迷宫n x n的范围内。如果越界直接返回false。然后判断迷宫grid[i][j]是否是障碍物‘#’。如果是返回false。如果所有格子都通过了检查则返回true。这里有一个极易出错的边界情况起点和终点的合法性。题目通常保证起点和终点是空地但我们需要用check函数来判断在t0时刻胖子能否站在起点在任意t时刻胖子能否站在终点必须确保这两个基本状态是合法的否则问题无解。在编码时务必在BFS开始前就对起点状态(sx, sy, 0)做一次check。2.2 状态去重与剪枝在三维BFS中状态空间是n * n * T其中T是可能的最大时间。如果不加以限制队列可能会非常庞大。因此有效的状态去重和剪枝至关重要。关键剪枝时间维度的单调性对于同一个坐标(x, y)如果我们在t1时刻访问过它那么在t2时刻t2 t1再次访问这个坐标通常是没有意义的甚至是浪费。因为BFS保证第一次到达某个状态的时间是最短的。如果你在t1时刻已经站在(x, y)那么你绝对没有必要在更晚的t2时刻再次到达这里。这意味着我们可以用一个二维数组vis[x][y]来记录到达(x, y)的最早时间。当尝试一个新状态(nx, ny, new_t)时如果new_t vis[nx][ny]我们就可以直接跳过这个状态无需入队。这个剪枝能极大地减少状态数。但请注意初始化时vis数组应设为一个很大的值如INFvis[sx][sy] 0。3. 代码实现与逐行解析理解了思路我们来看C的具体实现。我会将代码分成几个模块并详细解释每一部分的作用和易错点。#include iostream #include queue #include cstring using namespace std; const int N 310; // 假设迷宫最大为300x300多开一点空间 const int INF 0x3f3f3f3f; char grid[N][N]; // 存储迷宫 int n, k; // 迷宫大小体型变化时间间隔 int vis[N][N]; // 剪枝数组记录到达(x,y)的最早时间 // 方向数组上右下左 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; struct State { int x, y, time; // 中心点坐标当前时间 State(int _x, int _y, int _t) : x(_x), y(_y), time(_t) {} }; // 核心判断在time时刻中心在(cx,cy)的胖子是否合法 bool check(int cx, int cy, int time) { int r; // 体型半径 if (time k) r 2; else if (time 2 * k) r 1; else r 0; // 遍历胖子身体覆盖的正方形区域 for (int i cx - r; i cx r; i) { for (int j cy - r; j cy r; j) { // 1. 判断是否越界 if (i 0 || i n || j 0 || j n) return false; // 2. 判断是否是障碍物 if (grid[i][j] #) return false; } } return true; } int bfs(int sx, int sy, int ex, int ey) { // 初始化vis数组 memset(vis, 0x3f, sizeof(vis)); // 用INF填充 queueState q; // 起点状态合法性检查非常重要 if (!check(sx, sy, 0)) { return -1; // 起点就不合法问题可能无解但题目通常不会这样 } // 起点状态入队并标记 q.push(State(sx, sy, 0)); vis[sx][sy] 0; while (!q.empty()) { State cur q.front(); q.pop(); // 如果已经到达终点由于BFS性质当前时间就是最短时间 if (cur.x ex cur.y ey) { return cur.time; } // 操作1尝试向四个方向移动 for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; int nt cur.time 1; // 剪枝1如果新时间不优于历史记录跳过 if (nt vis[nx][ny]) continue; // 剪枝2移动后的状态合法性检查 if (!check(nx, ny, nt)) continue; // 状态合法入队并更新vis q.push(State(nx, ny, nt)); vis[nx][ny] nt; } // 操作2尝试原地等待1单位时间 int nt cur.time 1; // 剪枝同样判断时间优势和状态合法性 if (nt vis[cur.x][cur.y] check(cur.x, cur.y, nt)) { q.push(State(cur.x, cur.y, nt)); // 注意等待操作也可能更新当前点的最早到达时间 // 例如在某个点等待后变得更“瘦”从而能以更早的时间概念上允许后续移动 // 但实际上由于nt cur.timevis[cur.x][cur.y]在起点已被设为0这里通常不会更新。 // 更严谨的写法是如果nt vis[cur.x][cur.y]则更新。但在这个场景下等待操作主要是为了生成新状态而不是优化当前点的时间记录。 // 我们可以选择不更新vis或者更新。为了逻辑统一我们更新。 vis[cur.x][cur.y] nt; } } // 队列为空仍未到达终点说明无路可通 return -1; } int main() { cin n k; int sx, sy, ex, ey; for (int i 0; i n; i) { for (int j 0; j n; j) { cin grid[i][j]; if (grid[i][j] S) { sx i; sy j; grid[i][j] *; // 将起点标记为空地方便check函数判断 } else if (grid[i][j] T) { ex i; ey j; grid[i][j] *; // 将终点标记为空地 } } } int ans bfs(sx, sy, ex, ey); cout ans endl; return 0; }代码关键点解析数据结构选择使用struct State来封装状态三元组比用pairpairint,int, int更清晰。队列使用queueState。vis数组的初始化与使用memset(vis, 0x3f, sizeof(vis))是一种将数组初始化为一个很大值约10^9的常用技巧。vis[x][y]存储的是最早到达(x,y)的时间。因此只有当新状态的nt严格小于vis[nx][ny]时这个状态才可能带来更优的后续路径才需要入队。这个“严格小于”的判断是剪枝的核心。check函数的调用时机在bfs中有两个地方调用了check。一是在起点入队前确保起点合法二是在生成新状态移动或等待后判断新状态是否合法。千万不要在从队列中取出状态cur时判断其合法性因为能入队的状态必定是合法的。终点判断在从队列中取出状态cur后立即判断是否为终点。因为BFS按时间扩展第一次取出的终点状态对应的时间就是全局最短时间。等待操作的意义等待操作(cur.x, cur.y, cur.time1)可能会产生一个vis值更大的状态因为时间增加了。但是这个状态对于未来路径的探索是必要的。例如胖子在一个死胡同口需要等待变瘦才能转身进入旁边的窄路。虽然等待后vis值变大了但这个状态是通往终点的必经中间状态。因此等待状态也需要入队。4. 调试技巧与常见“坑点”实录即便思路清晰代码写起来也难免掉坑。下面是我在多次实现和教学中总结的常见问题几乎每个问题都曾让不少选手“栽跟头”。4.1 体型半径计算的边界错误这是最高频的错误之一。题目描述是“经过k秒后”体型变化。注意这个“经过后”的含义。错误理解t k时胖子已经完成了第一次收缩。所以当t k时半径应该是1而不是2。正确理解在时间区间[0, k)内半径r2在[k, 2k)内r1在[2k, ∞)内r0。 因此check函数中的判断条件必须是if (time k) r 2; else if (time 2 * k) r 1; // 注意这里是 time 2*k 不是 else r 0;如果写成if (time k)那么在tk时胖子会被误认为还是大胖子可能导致在狭窄路口提前尝试通过而撞墙或者相反该通过时却不敢通过。4.2 状态去重与剪枝的逻辑矛盾vis数组的剪枝逻辑“nt vis[nx][ny]则跳过”非常强大但必须理解其前提BFS寻找的是最短时间。对于同一个坐标更晚到达的状态不可能产生比更早到达状态更优的全局解。这个前提在绝大多数情况下成立。但是有一个极其隐蔽的例外“等待”操作产生的状态。考虑这样一个场景胖子在t0时刻以r2的体型到达点Avis[A]0。然后他在A点等待在tk时刻他变成了r1的体型。这个新状态(A, k)的ntk是大于vis[A]0的。按照我们的剪枝逻辑这个状态会被跳过然而这个状态可能是至关重要的。因为从(A, 0)状态出发胖子可能由于体型太大无法进入A点旁边的窄路B但从(A, k)状态体型变小出发他就可以进入B点。解决方案我们需要重新思考vis数组的含义。它不应该简单记录“到达某个坐标的最早时间”而应该记录“在某个坐标且能以某种体型或更小体型自由行动的最早时间”。更精确地说由于体型只随时间单调变小我们可以认为如果在时间t1以体型r1到达(x,y)那么在t2(t1)时刻以更小的体型r2到达同一点这个新状态可能仍然有价值如果r2能提供新的移动可能性比如通过更窄的路。因此一个更鲁棒的剪枝策略是使用三维vis数组vis[x][y][r]。但这样会增大空间开销。一个更巧妙的优化是我们意识到对于同一个坐标如果我们在更晚的时间以更小的体型到达我们只需要保留那个体型最小的状态吗不因为时间也是成本。实际上标准的vis[x][y]记录最早到达时间的剪枝在“大胖子走迷宫”这个问题中依然是正确的。为什么呢因为如果存在一条路径它在更晚的时间t2以更小的体型到达(x,y)并最终到达终点那么一定存在另一条路径它在更早的时间t1到达(x,y)后原地等待到t2时刻然后再执行相同的后续操作。这条新路径的终点到达时间不会比原路径晚。所以vis数组记录最早到达时间并进行剪枝不会错过最优解。上面的“隐蔽例外”场景中从(A,0)状态我们可以通过执行“等待”操作直接生成(A,k)状态而无需依赖从其他路径在tk时刻“首次”到达A。因此我们代码中对于等待操作也将其视为一个可生成的新状态并入队这是正确的。而vis剪枝跳过的是那些从其他路径、在更晚时间、到达同坐标的状态这些状态确实是冗余的。所以我们代码中的剪枝逻辑是没问题的。关键在于“等待”操作是在当前状态的基础上生成新状态而不是从其他路径过来。我们代码中对于等待操作判断if (nt vis[cur.x][cur.y] ...)在第一次到达cur点时vis[cur.x][cur.y]已经被设为cur.time而nt cur.time1所以nt不可能小于vis这个等待状态会被自己的剪枝逻辑跳过这似乎是个问题修正这正是另一个坑点对于等待操作我们不应该用vis来剪枝或者应该用不同的逻辑。因为等待操作是在同一个坐标产生一个时间更晚的状态这个状态是有意义的为了变瘦。如果我们用nt vis[cur.x][cur.y]来剪枝所有的等待操作都会被剪掉这显然是错误的。正确的处理方式将移动和等待分开看待。对于移动到新坐标(nx, ny)我们使用vis[nx][ny]进行剪枝。对于等待在原地(cur.x, cur.y)我们不应该使用vis来剪枝或者我们需要一个额外的机制。一个简单的方法是不对此进行剪枝直接判断合法性后入队。但这样可能导致无限循环的等待原地不停等待。为了避免这种情况我们需要一个额外的标记记录在某个坐标最后一次以某种体型等待的时间这又复杂了。更简洁实用的方案放弃对等待操作使用vis剪枝但限制等待的总时长。因为体型只在2k时间内变化之后就不再变化。所以在任何一点有意义的等待时间最多到2k。我们可以这样修改等待操作的代码// 操作2尝试原地等待。只有当前时间小于2k时等待才有意义体型还会变。 if (cur.time 2 * k) { // 只有体型还会变化时等待才有意义 int nt cur.time 1; // 不进行vis剪枝直接判断状态合法性 if (check(cur.x, cur.y, nt)) { q.push(State(cur.x, cur.y, nt)); // 注意这里不更新vis[cur.x][cur.y]因为这不是一个“更早”的到达。 } }这个方案更清晰也避免了剪枝逻辑的纠缠。4.3 输入处理的细节题目输入中起点和终点通常用字符‘S’和‘T’表示。在存储迷宫grid时我们需要将它们替换成可通行的空地符号如‘*’因为check函数只检查‘#’障碍物。如果忘记替换check函数会认为起点和终点是障碍物导致判断错误。4.4 时间复杂度与空间复杂度分析时间复杂度最坏情况下每个状态(x, y, t)都会被访问一次。t的最大值是多少在最坏情况下比如一个很大的空旷迷宫需要等待很久胖子可能需要走到迷宫最远处时间t最大约为n 2k。因此状态数上界约为O(n^2 * (n2k))。由于BFS每个状态扩展5个新状态4个移动1个等待常数较大但对于n300, k100的竞赛数据通常是可以接受的。空间复杂度主要是队列和vis数组的开销为O(n^2)。5. 测试用例与思维拓展为了验证代码正确性需要设计多种测试用例。基础测试用例1无需等待5 10 S**** ***** ***** ***** ****T答案应为8曼哈顿距离。检查BFS是否在无等待情况下能找到最短路径。基础测试用例2必须等待5 1 S###* #***# #*#*# #***# *###T迷宫中间有一条狭窄的横向通道只有一行是空地。大胖子(r2)无法通过必须等待至少1秒变为中胖子(r1)才能通过。需要计算包含等待时间的最短路径。复杂测试用例3等待时机选择7 2 ***#*** ***#*** ***#*** S##*##T ***#*** ***#*** ***#***迷宫被一条垂直的墙分开只有中间一个格子是通路。大胖子(r2)过不去需要等待。是应该一开始就在起点等还是走到墙边再等BFS应该能自动找出最优策略。思维拓展如果胖子体型变化规律不是分段常数而是随时间连续变化比如半径r max(0, 2 - t/k)该如何处理这时状态的时间维度就几乎是连续的了。一种近似方法是离散化时间或者使用优先队列Dijkstra算法将时间作为距离成本。如果迷宫是动态变化的比如某些障碍物会周期性出现/消失又该如何这将成为“时间依赖型迷宫”问题状态需要增加一维来表示迷宫所处的周期相位复杂度会进一步上升。如何输出最短路径而不仅仅是时间需要在State结构体中增加一个pre指针或记录前驱状态(px, py, pt)最后从终点状态反向回溯即可。这道“大胖子走迷宫”题从一个生动的设定出发深入考察了搜索算法中“状态”这一核心概念的理解。它告诉我们当问题中涉及随时间变化的属性时必须考虑将其纳入状态定义中。而“等待”作为一种特殊的行动其重要性不亚于移动。通过这道题的锤炼对于状态空间搜索的理解无疑会上一个大台阶。在编码时务必细心处理体型变化的边界、状态去重的逻辑以及等待操作的特殊性多构造边缘用例测试才能确保代码的万无一失。