1. 项目概述当“大胖子”遇上迷宫最近在复盘蓝桥杯的经典题目翻到了第十届国赛Java B组的第8题——“大胖子走迷宫”。这题目名字听起来就挺有意思不是简单的寻路而是带着“体型”变化的约束去走迷宫。很多朋友在初次接触时会觉得这不就是个BFS广度优先搜索嘛但一上手就发现普通的BFS模板在这里会“卡壳”因为我们的角色不是一成不变的。这道题的精髓恰恰在于将时间维度与空间状态巧妙地结合模拟了一个角色随时间“膨胀”和“收缩”的动态过程再与静态的迷宫障碍进行交互。它考察的不仅是基础的搜索算法更是对状态定义、边界条件处理和模拟能力的综合运用。今天我就结合自己多次解题和教学的经验把这个题的“里子”和“面子”都拆开揉碎了讲清楚从问题本质分析到代码逐行实现最后再附上调试时最容易踩的坑。简单来说题目给你一个N x N的迷宫里面有障碍物#和空地.。你控制一个“大胖子”初始时他非常“胖”占地面积是5x5以自身中心点算向上下左右各延伸2格。迷宫入口在左上角(2,2)出口在右下角(N-3, N-3)。这个胖子有个特点他会随着时间变瘦具体规则是前K个单位时间他保持5x5的体型接下来K个单位时间他收缩为3x3K个单位时间后他最终变为正常的1x1体型并保持不变。在移动时他的整个“占地范围”内都不能有障碍物#。他每次可以向上、下、左、右移动一格或者选择原地等待等待也会消耗时间。我们的目标就是找到他从入口到出口的最短时间。所以这不仅仅是一个找路的问题它是一个在时间-空间-状态三维空间里的寻优问题。普通的二维坐标BFS在这里失效了我们必须把“时间”和“体型”也作为状态的一部分。接下来我们就一步步拆解这个有趣的挑战。2. 核心思路与状态定义从二维到三维的思维跃迁面对这个问题最直接的误区就是试图用标准的二维BFS去解决。你会定义一个visited[x][y]数组来记录某个坐标是否被访问过然后从起点开始扩散。但很快就会发现行不通因为同一个坐标(x, y)在不同的时间点由于胖子的体型不同其可达性是完全不一样的。比如在时间t0时胖子是5x5他可能因为左侧有障碍而无法移动到(x, y)但到了时间t10他可能已经收缩为3x3同样的移动就可能变得合法。2.1 为什么需要三维状态这是本题最核心的思维转换点。我们必须将时间和体型纳入我们的状态考量。一个最直观的方法是使用三维状态数组visited[x][y][t]。但这面临一个问题时间t的上限是多少题目没有明确给出理论上如果迷宫非常绕时间可能很大三维数组会消耗巨大的内存甚至不可行。更优雅且高效的做法是将“体型”作为状态的第三维而不是时间。因为体型是随时间变化的但它只有有限的几种状态本题中是3种5x5 3x3 1x1。我们定义状态为(x, y, size)其中size表示当前时刻胖子的“半径”。注意这里说的“半径”是指从中心点向四周扩展的格数。初始体型5x5半径r23x3对应r11x1对应r0。那么时间信息去哪了时间隐含在BFS的步数或者说队列扩展的轮次中。当我们从状态A扩展到状态B时如果执行的是移动操作那么状态B的时间就是状态A的时间1如果是等待操作状态B的时间也是状态A的时间1。时间就是BFS的深度。我们不需要显式存储时间只需要在队列节点里记录当前时间即可。2.2 状态转移的设计定义了状态(x, y, size)后我们需要设计如何从一个状态转移到另一个状态。这里有五种可能的动作上、下、左、右、原地等待。但每个动作能否执行都需要进行严格的合法性校验。移动动作上下左右首先目标坐标(nx, ny)必须在迷宫范围内。其次也是最重要的以(nx, ny)为中心当前体型size为半径构成的方形区域内不能有任何障碍物#。这需要遍历一个(2*size1) x (2*size1)的区域进行检查。如果校验通过则新状态为(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]; QueueState 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*size1的正方形区域内不能有障碍物‘#’ // 计算这个区域的左上角和右下角坐标 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流程我们使用QueueState来进行广度优先搜索。起点状态(2,2,0,2)首先入队。每次从队首取出一个状态首先判断是否为终点如果是则直接输出时间BFS性质保证这是最短时间。然后进行状态扩展移动扩展生成四个方向的下一个坐标计算新时间和新体型调用isValid进行全面校验合法则标记并入队。等待扩展计算等待后的新时间和新体型。执行关键剪枝如果新旧体型相同则跳过。否则检查新状态(x, y, newSize)是否已被访问未访问则标记并入队。这个循环持续到队列为空理论上不会因为题目保证有解或找到终点为止。4. 调试心得与常见“坑点”实录这道题在实现时有几个地方特别容易出错我自己和学生们都踩过不少坑。4.1 坑点一体型检查的区域计算错误这是最常见的错误。题目说“占地范围”很多人会误解。错误理解1认为体型是(2*size1)的矩形但检查时只检查了中心点上下左右各size格漏掉了角落。必须检查整个矩形区域。错误理解2在计算区域边界时直接写循环for(int ix-size; ixsize; i)但没有先判断x-size和xsize是否在数组下标范围内。如果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那么无论等待多少步只要tK仍然小于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]就会犯下开头说的错误——认为同一个坐标只需要访问一次。例如胖子可能在时间t5时以5x5体型尝试进入(x,y)失败因为胖卡住了但在时间t15时以1x1体型成功进入(x,y)。如果二维判重在t5失败时标记了visited[x][y]true那么t15时这个可行的状态就会被错误地剪掉导致找不到路径。4.5 性能优化小技巧虽然本题的数据规模N300下上述BFS算法足够通过但养成优化习惯总是好的。提前计算区域并缓存对于每个size0,1,2其需要检查的偏移量是固定的。我们可以预先计算好三个Listint[]存储对于每个size需要检查的相对于中心点的(dx, dy)坐标列表。这样在isValid中就不需要用双层for循环计算边界再遍历而是直接遍历这个列表中的每个偏移位置进行检查。对于size2检查25个点来说效率提升不明显但对于追求极致性能是有帮助的。使用循环队列或数组模拟队列LinkedList作为队列在大量入队出队时有一定开销。在竞赛中如果已知状态数上限可以预先分配一个大的数组用两个指针head和tail来模拟队列速度更快。5. 测试用例与模拟推演理论说得再多不如跑几个例子来得实在。我们设计一个简单的迷宫来模拟一下算法的执行过程。假设 N5, K2。迷宫如下‘.‘为空地‘#‘为障碍..... .###. ..... .###. .....起点(2,2)终点(2,2)这里为了简化起点即终点主要看状态变化。初始queue [(2,2,0,2)],visited[2][2][2]true。弹出(2,2,0,2)时间0体型半径25x5。尝试移动。由于是5x5检查范围很大上下左右移动都会导致其占地区域超出地图边界例如向上移动中心到(1,2)其区域从(-1,0)到(3,4)左上角出界所以所有移动均不合法。尝试等待waitTime1,waitSize getSize(1,2)由于12所以waitSize仍为2。waitSize cur.size触发剪枝等待状态不加入队列。此时队列为空。结果队列空未找到终点等等起点就是终点我们在弹出第一个状态时就应该判断并返回时间0。所以我们的BFS循环中判断终点的代码if (cur.x endX ...)必须放在处理动作之前。上面的模拟步骤2中在尝试移动和等待之前就应该先判断cur是否为终点如果是直接输出cur.time即0。所以算法是正确的。再来看一个需要等待的例子。设想一个狭窄的通道初始胖子过不去必须等变瘦。通过这类模拟可以非常清晰地理解状态是如何随着时间和动作演变的以及剪枝逻辑如何起作用。自己动手画一画状态转移图是理解这类搜索题的最佳方式。6. 总结与思维延伸“大胖子走迷宫”是一道非常经典的BFS变种题它成功地将时间维度融入了状态空间。解决它的关键在于跳出二维平面的思维定式构建(坐标, 体型)或者更广义的(坐标, 附加状态)的三维状态模型。一旦状态定义正确剩下的就是标准的BFS框架和细致的条件检查。从这道题可以延伸出去很多复杂的搜索问题都可以用类似的“状态压缩”思想来解决。比如带有钥匙和门的迷宫状态坐标已获得的钥匙集合。在特定步数后能力会变化的角色。需要收集所有物品的最短路径问题状态坐标物品收集情况。其核心思想都是当问题中除了位置信息外还有其他影响决策或可达性的变量时把这些变量一并纳入状态定义中从而将问题转化为在一个高维空间中的标准搜索问题。最后在编码实现时务必注意细节边界检查、条件判断的顺序、有效的剪枝策略。多构造一些极端和小规模的测试用例比如迷宫很小、K很大或很小、起点终点很近等用打印日志或调试器一步步跟踪状态变化是快速定位BUG的不二法门。希望这篇详细的拆解能帮你不仅AC这道题更能掌握这一类问题的通用解法。