蓝桥杯经典题解析：BFS三维状态建模解决动态体型走迷宫问题-编程实验室

1. 项目概述：当“大胖子”遇上迷宫

最近在复盘蓝桥杯的经典题目，翻到了第十届国赛Java B组的第8题——“大胖子走迷宫”。这题目名字听起来就挺有意思，不是简单的寻路，而是带着“体型”变化的约束去走迷宫。很多朋友在初次接触时，会觉得这不就是个BFS（广度优先搜索）嘛，但一上手就发现，普通的BFS模板在这里会“卡壳”，因为我们的角色不是一成不变的。这道题的精髓，恰恰在于将时间维度与空间状态巧妙地结合，模拟了一个角色随时间“膨胀”和“收缩”的动态过程，再与静态的迷宫障碍进行交互。它考察的不仅是基础的搜索算法，更是对状态定义、边界条件处理和模拟能力的综合运用。今天，我就结合自己多次解题和教学的经验，把这个题的“里子”和“面子”都拆开揉碎了讲清楚，从问题本质分析到代码逐行实现，最后再附上调试时最容易踩的坑。

简单来说，题目给你一个N x N的迷宫，里面有障碍物#和空地.。你控制一个“大胖子”，初始时他非常“胖”，占地面积是5x5（以自身中心点算，向上下左右各延伸2格）。迷宫入口在左上角(2,2)，出口在右下角(N-3, N-3)。这个胖子有个特点：他会随着时间变瘦！具体规则是：前K个单位时间，他保持5x5的体型；接下来K个单位时间，他收缩为3x3；K个单位时间后，他最终变为正常的1x1体型并保持不变。在移动时，他的整个“占地范围”内都不能有障碍物#。他每次可以向上、下、左、右移动一格，或者选择原地等待（等待也会消耗时间）。我们的目标就是找到他从入口到出口的最短时间。

所以，这不仅仅是一个找路的问题，它是一个在时间-空间-状态三维空间里的寻优问题。普通的二维坐标BFS在这里失效了，我们必须把“时间”和“体型”也作为状态的一部分。接下来，我们就一步步拆解这个有趣的挑战。

2. 核心思路与状态定义：从二维到三维的思维跃迁

面对这个问题，最直接的误区就是试图用标准的二维BFS去解决。你会定义一个visited[x][y]数组来记录某个坐标是否被访问过，然后从起点开始扩散。但很快就会发现行不通，因为同一个坐标(x, y)，在不同的时间点，由于胖子的体型不同，其可达性是完全不一样的。比如，在时间t=0时，胖子是5x5，他可能因为左侧有障碍而无法移动到(x, y)；但到了时间t=10，他可能已经收缩为3x3，同样的移动就可能变得合法。

2.1 为什么需要三维状态？

这是本题最核心的思维转换点。我们必须将时间和体型纳入我们的状态考量。一个最直观的方法是使用三维状态数组：visited[x][y][t]。但这面临一个问题：时间t的上限是多少？题目没有明确给出，理论上如果迷宫非常绕，时间可能很大，三维数组会消耗巨大的内存，甚至不可行。

更优雅且高效的做法是，将“体型”作为状态的第三维，而不是时间。因为体型是随时间变化的，但它只有有限的几种状态（本题中是3种：5x5， 3x3， 1x1）。我们定义状态为(x, y, size)，其中size表示当前时刻胖子的“半径”。注意，这里说的“半径”是指从中心点向四周扩展的格数。初始体型5x5，半径r=2；3x3对应r=1；1x1对应r=0。

那么，时间信息去哪了？时间隐含在BFS的步数（或者说队列扩展的轮次）中。当我们从状态A扩展到状态B时，如果执行的是移动操作，那么状态B的时间就是状态A的时间+1；如果是等待操作，状态B的时间也是状态A的时间+1。时间就是BFS的深度。我们不需要显式存储时间，只需要在队列节点里记录当前时间即可。

2.2 状态转移的设计

定义了状态(x, y, size)后，我们需要设计如何从一个状态转移到另一个状态。这里有五种可能的动作：上、下、左、右、原地等待。但每个动作能否执行，都需要进行严格的合法性校验。

移动动作（上下左右）：首先，目标坐标(nx, ny)必须在迷宫范围内。其次，也是最重要的，以(nx, ny)为中心，当前体型size为半径构成的方形区域内，不能有任何障碍物#。这需要遍历一个(2*size+1) x (2*size+1)的区域进行检查。如果校验通过，则新状态为(nx, ny, nextSize)，其中nextSize是根据当前总时间（即父节点时间+1）计算出的新体型。
等待动作：坐标不变，体型可能发生变化。新状态为(x, y, nextSize)，其中nextSize根据新的时间（父节点时间+1）计算。

这里的关键在于nextSize的计算函数。它只依赖于总耗时totalTime（从起点出发到当前状态所经过的时间）。根据题目：

如果totalTime < K，则size = 2(5x5)。
如果K <= totalTime < 2*K，则size = 1(3x3)。
如果totalTime >= 2*K，则size = 0(1x1)。

2.3 判重与剪枝

我们使用一个三维数组visited[x][y][s]来记录某个状态是否被访问过。其中s是体型索引，可以映射为0,1,2分别代表半径0,1,2。为什么这样能有效判重？因为BFS的特性是第一次到达某个状态所用的时间一定是最短的。如果我们之前已经以更短的时间到达过状态(x, y, s)，那么后续再以更长时间到达这个状态就是无效的，可以直接剪枝。

这里有一个极其重要的优化点：对于等待操作，如果等待前后体型size没有发生变化，那么这个等待就是完全无效的，应该直接跳过。例如，在总时间t < K的阶段，无论等待多久，体型始终是5x5。在这种情况下，原地等待除了浪费时间，不会带来任何状态改变，所以不应该将“原地等待且体型不变”的状态加入队列。这能避免大量的无效状态膨胀，防止队列爆炸。

3. 代码实现与逐行解析

理论分析完毕，我们来看具体的代码实现。我将使用Java语言，并附上详细的注释。

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class FatManMaze { // 方向数组：上，下，左，右 static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static class State { int x, y; // 当前中心坐标 int time; // 从起点到当前状态所花时间 int size; // 当前体型半径 (0,1,2) public State(int x, int y, int time, int size) { this.x = x; this.y = y; this.time = time; this.size = size; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); sc.nextLine(); // 消耗换行符 char[][] maze = new char[N][N]; for (int i = 0; i < N; i++) { maze[i] = sc.nextLine().toCharArray(); } // 起点和终点坐标（题目已给出） int startX = 2, startY = 2; int endX = N - 3, endY = N - 3; // 访问标记数组 visited[x][y][size] boolean[][][] visited = new boolean[N][N][3]; Queue<State> queue = new LinkedList<>(); // 初始状态：起点，时间0，体型为最大（半径2） queue.offer(new State(startX, startY, 0, 2)); visited[startX][startY][2] = true; while (!queue.isEmpty()) { State cur = queue.poll(); // 如果已经到达终点，输出时间（BFS首次到达即为最短时间） if (cur.x == endX && cur.y == endY) { System.out.println(cur.time); return; } // 动作1：尝试向四个方向移动 for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; int nTime = cur.time + 1; // 计算移动后的体型 int nSize = getSize(nTime, K); // 检查移动是否合法 if (isValid(nx, ny, nSize, N, maze, visited)) { visited[nx][ny][nSize] = true; queue.offer(new State(nx, ny, nTime, nSize)); } } // 动作2：尝试原地等待 int waitTime = cur.time + 1; int waitSize = getSize(waitTime, K); // 关键剪枝：只有等待后体型发生变化，这次等待才有意义 if (waitSize != cur.size) { // 等待时坐标不变，只需要检查等待后的新状态是否被访问过 if (!visited[cur.x][cur.y][waitSize]) { visited[cur.x][cur.y][waitSize] = true; queue.offer(new State(cur.x, cur.y, waitTime, waitSize)); } } } // 理论上题目保证有解，所以不会执行到这里 // System.out.println(-1); } // 根据当前时间计算体型半径 static int getSize(int time, int K) { if (time < K) { return 2; // 5x5 } else if (time < 2 * K) { return 1; // 3x3 } else { return 0; // 1x1 } } // 检查一个状态是否合法可到达 static boolean isValid(int x, int y, int size, int N, char[][] maze, boolean[][][] visited) { // 1. 中心点坐标必须在迷宫内 if (x < 0 || x >= N || y < 0 || y >= N) { return false; } // 2. 该状态是否已被访问过（判重） if (visited[x][y][size]) { return false; } // 3. 最核心的检查：以(x,y)为中心，边长为2*size+1的正方形区域内不能有障碍物‘#’ // 计算这个区域的左上角和右下角坐标 int top = x - size; int bottom = x + size; int left = y - size; int right = y + size; // 首先检查这个区域是否完全在迷宫内 if (top < 0 || bottom >= N || left < 0 || right >= N) { return false; } // 遍历该区域每一个格子 for (int i = top; i <= bottom; i++) { for (int j = left; j <= right; j++) { if (maze[i][j] == '#') { return false; // 发现障碍物，非法 } } } // 所有检查通过，状态合法 return true; } }

3.1 关键函数解析

getSize(int time, int K)：这个函数是状态转换的枢纽。它根据从起点开始的总时间，确定当前应有的体型。注意，这里的time是累积时间，不是步数。在BFS中，每个节点携带的time值就是从起点到该节点的耗时。

isValid(...)：这是算法的核心校验函数，它综合判断一个目标状态是否可达。其逻辑顺序很重要：

坐标边界检查。
状态判重检查（visited数组）。这一步能剪掉大量重复搜索。
体型区域障碍物检查。这是计算开销最大的一步，需要遍历一个方形区域。我们通过预先计算区域的上下左右边界，并先检查该区域是否出界，可以避免无效的循环。特别注意：必须先检查区域边界，再遍历内部。否则，如果区域本身已经超出迷宫，遍历时会引发数组越界异常。

3.2 队列与BFS流程

我们使用Queue<State>来进行广度优先搜索。起点状态(2,2,0,2)首先入队。每次从队首取出一个状态，首先判断是否为终点，如果是则直接输出时间（BFS性质保证这是最短时间）。

然后进行状态扩展：

移动扩展：生成四个方向的下一个坐标，计算新时间和新体型，调用isValid进行全面校验，合法则标记并入队。
等待扩展：计算等待后的新时间和新体型。执行关键剪枝：如果新旧体型相同，则跳过。否则，检查新状态(x, y, newSize)是否已被访问，未访问则标记并入队。

这个循环持续到队列为空（理论上不会，因为题目保证有解）或找到终点为止。

4. 调试心得与常见“坑点”实录

这道题在实现时，有几个地方特别容易出错，我自己和学生们都踩过不少坑。

4.1 坑点一：体型检查的区域计算错误

这是最常见的错误。题目说“占地范围”，很多人会误解。

错误理解1：认为体型是(2*size+1)的矩形，但检查时只检查了中心点上下左右各size格，漏掉了角落。必须检查整个矩形区域。
错误理解2：在计算区域边界时，直接写循环for(int i=x-size; i<=x+size; i++)，但没有先判断x-size和x+size是否在数组下标范围内。如果x-size < 0，那么maze[i][j]就会数组越界。务必先判断区域整体是否在迷宫内，这是isValid函数中那个if (top < 0 || ...)判断的作用。

注意：区域整体越界和内部有障碍物是两种不同的非法情况，都应返回false。

4.2 坑点二：对“时间”的理解混淆

题目中有两个“K”，以及“前K个单位时间”的描述。容易混淆的点：

节点时间 vs 体型阶段：每个State节点里存储的time，是从起点开始到该节点的总耗时。而函数getSize(time, K)正是基于这个总耗时来判断体型。不要和“在当前体型阶段内待了多久”搞混。
等待操作的意义：等待的唯一目的，就是让总时间time增加，从而可能触发体型变化（从5x5变3x3，或从3x3变1x1）。如果当前总时间t满足t < K，那么无论等待多少步，只要t+K仍然小于K，体型就不会变。所以我们的剪枝逻辑if (waitSize != cur.size)非常关键，它直接去除了大量原地踏步的无效状态。

4.3 坑点三：起点与终点的处理

题目明确入口是(2,2)，出口是(N-3, N-3)。这是为了给初始5x5的体型留出空间（左上角需要(0,0)到(4,4)的区域无障碍）。在代码中，我们直接使用这些坐标即可。但有一点需要注意：到达终点时，不要求体型一定是1x1。只要胖子的中心点移动到了终点坐标(N-3, N-3)，无论此时他是胖是瘦，都算成功。所以我们的终止条件是if (cur.x == endX && cur.y == endY)，与cur.size无关。

4.4 坑点四：状态判重的维度

我们必须使用三维数组visited[x][y][size]。如果只用二维visited[x][y]，就会犯下开头说的错误——认为同一个坐标只需要访问一次。例如，胖子可能在时间t=5时以5x5体型尝试进入(x,y)失败（因为胖，卡住了），但在时间t=15时以1x1体型成功进入(x,y)。如果二维判重，在t=5失败时标记了visited[x][y]=true，那么t=15时这个可行的状态就会被错误地剪掉，导致找不到路径。

4.5 性能优化小技巧

虽然本题的数据规模（N<=300）下，上述BFS算法足够通过，但养成优化习惯总是好的。

提前计算区域并缓存：对于每个size（0,1,2），其需要检查的偏移量是固定的。我们可以预先计算好三个List<int[]>，存储对于每个size，需要检查的相对于中心点的(dx, dy)坐标列表。这样在isValid中就不需要用双层for循环计算边界再遍历，而是直接遍历这个列表中的每个偏移位置进行检查。对于size=2（检查25个点）来说，效率提升不明显，但对于追求极致性能是有帮助的。
使用循环队列或数组模拟队列：LinkedList作为队列在大量入队出队时有一定开销。在竞赛中，如果已知状态数上限，可以预先分配一个大的数组，用两个指针head和tail来模拟队列，速度更快。

5. 测试用例与模拟推演

理论说得再多，不如跑几个例子来得实在。我们设计一个简单的迷宫来模拟一下算法的执行过程。

假设 N=5, K=2。迷宫如下（‘.‘为空地，‘#‘为障碍）：

..... .###. ..... .###. .....

起点(2,2)，终点(2,2)（这里为了简化，起点即终点，主要看状态变化）。

初始：queue = [(2,2,0,2)],visited[2][2][2]=true。
弹出(2,2,0,2)：时间0，体型半径2（5x5）。尝试移动。由于是5x5，检查范围很大，上下左右移动都会导致其占地区域超出地图边界（例如向上移动，中心到(1,2)，其区域从(-1,0)到(3,4)，左上角出界），所以所有移动均不合法。尝试等待：waitTime=1,waitSize = getSize(1,2)，由于1<2，所以waitSize仍为2。waitSize == cur.size，触发剪枝，等待状态不加入队列。此时队列为空。
结果：队列空，未找到终点？等等，起点就是终点，我们在弹出第一个状态时就应该判断并返回时间0。所以我们的BFS循环中，判断终点的代码if (cur.x == endX ...)必须放在处理动作之前。上面的模拟步骤2中，在尝试移动和等待之前，就应该先判断cur是否为终点，如果是，直接输出cur.time（即0）。所以算法是正确的。