1. 项目概述当“大胖子”遇上迷宫最近在复盘蓝桥杯的经典题目翻到了第十届国赛Java B组的第8题——“大胖子走迷宫”。这题目名字起得挺有意思一听就不是普通的迷宫寻路。普通的迷宫题角色通常是一个点上下左右移动避开墙就行。但“大胖子”意味着角色有体积不是点而是一个占据多个格子的“方块”。这就让问题一下子复杂起来了胖子在狭窄的通道里怎么转身怎么判断会不会卡住什么时候能“瘦下来”通过更窄的路这其实是一个典型的网格图上的状态搜索BFS/DFS问题但引入了时间维度和角色尺寸变化这两个关键变量。它考察的不仅仅是基础的图遍历算法更是对状态定义、边界条件处理和模拟能力的综合运用。很多同学初次接触时容易用普通BFS去套结果要么漏解要么超时根本原因就在于没有把“胖子”这个核心约束条件建模到搜索状态里。我自己在实现和教学过程中发现这道题有几个非常经典的“坑点”一是对“占据”多个格子的碰撞检测逻辑容易写错二是对“随时间变瘦”这个动态规则的理解和实现三是BFS中状态去重的关键。接下来我就结合这道题的典型数据把从问题分析、思路构建、代码实现到调试优化的完整过程拆解一遍并分享一些我踩过的坑和总结的技巧。2. 问题核心与建模思路拆解2.1 题目场景还原与约束分析我们先抛开代码把题目描述用更工程化的语言翻译一遍。题目通常会给一个n x n的字符矩阵表示迷宫‘’表示墙障碍物‘.’表示空地。一个“大胖子”小明初始时非常胖横向和纵向都占据了5个格子即一个5x5的方块。他每移动一步需要1单位时间。同时他有一个神奇的技能随着时间的推移他会变瘦。具体规则是从第0分钟开始到第k分钟含他是5x5的大小从第k1分钟开始到第2k分钟含他会变成3x3的大小从第2k1分钟开始及以后他会恢复成正常的1x1大小即一个点。这里的k是题目给定的参数。目标是找到小明从起点(xs, ys)走到终点(xe, ye)的最短时间。他只能上下左右移动每次移动一格以他中心点的移动为准。移动的前提是在移动完成后的那个时间点他身体所占据的所有格子都必须在迷宫范围内且都不是墙。这里的关键约束有三个动态尺寸胖子的尺寸是随时间变化的函数size(t)。碰撞检测移动是否合法需要检查目标位置为中心、当前尺寸为边长的正方形区域内所有格子。状态依赖时间能否从一个点移动到其相邻点不仅取决于这两个点的位置还取决于到达新点的时间因为时间决定了你此刻的胖瘦从而决定了这次移动是否合法。2.2 为什么不能用普通BFS普通的BFS求迷宫最短路状态就是坐标(x, y)用一个visited[x][y] true记录是否访问过。因为对于无权图每一步代价为1第一次访问某个点的距离就是最短距离。但在这个问题里这个性质被破坏了。原因在于从不同路径、在不同时间到达同一个坐标(x, y)其后续的可达性可能是不同的。举个例子有一条狭窄的通道宽度为1格。如果你在时间t5此时你还是5x5的胖子到达通道口的格子A你无法进入通道。但如果你在A点等待到时间t10此时你已变成1x1的瘦子你就可以进去了。如果你用普通BFS在t5第一次访问A点时就把visited[A]标记为真那么后面那条“在A点等待一段时间再进去”的更优路径就会被错误地剪掉因为BFS认为这个点已经访问过了。所以这个问题的状态必须是二维的(x, y, t)或者(x, y, s)其中s代表当前尺寸。由于尺寸是时间的函数两者等价。我们需要记录在时间t到达(x, y)这个状态。不同的t即使坐标相同也是不同的状态。2.3 状态空间搜索设计我们选择BFS进行搜索因为它天然适合求解边权相等的最短路问题。我们需要设计一个队列队列中的元素是一个状态(x, y, time)。状态转移从当前状态(x, y, t)可以转移到哪些新状态移动向上下左右四个方向移动一格得到新坐标(nx, ny)新时间t1。转移的前提是在时间t1以(nx, ny)为中心以size(t1)为边长的正方形区域内所有格子合法。停留停留在原地时间t1。这对应了“等待变瘦”的策略。转移前提是在时间t1以(x, y)为中心以size(t1)为边长的正方形区域内所有格子合法。注意停留也需要检查合法性因为随着你变瘦你之前占据的某些格子可能已经是墙虽然通常起点和空地不会但严谨起见需要检查。去重与剪枝我们需要一个visited[x][y][s]数组来记录状态是否被访问过。这里s是尺寸135。因为时间可能很大但尺寸只有3种。当我们在时间t以尺寸s访问(x, y)时如果这个状态已经访问过就可以跳过。这里有一个关键剪枝如果我们在更早的时间t1以相同或更灵活的尺寸比如1x1比3x3灵活访问过这个点那么当前这条路径一定不是最优的后续路径的起点可以剪掉。但为了简单起见我们可以严格记录(x, y, s)是否被访问因为如果先以瘦子状态访问了某点后续以胖子状态再访问胖子的行动能力更差不可能产生更好的结果。终止条件当从队列中取出状态(x, y, t)且(x, y)等于终点坐标时此时的t就是最短时间。因为BFS是按时间步数层层扩展的第一次到达终点的时间一定是最短的。3. 关键实现细节与“踩坑”实录理论思路清晰后实现起来还有一大堆细节魔鬼。下面我结合代码片段逐一拆解。3.1 数据结构与输入处理import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n, k; static char[][] maze; static boolean[][][] visited; // visited[x][y][size_index] static int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); k sc.nextInt(); maze new char[n][n]; // visited[x][y][s] s:0-1, 1-3, 2-5 visited new boolean[n][n][3]; for (int i 0; i n; i) { maze[i] sc.next().toCharArray(); } // 起点和终点通常固定为(2,2)和(n-3, n-3)因为胖子初始占5格中心在(2,2) int ans bfs(2, 2, n-3, n-3); System.out.println(ans); sc.close(); } }注意1起点终点坐标。题目描述中起点和终点是“小明的位置”这个位置指的是他身体的中心点。由于初始是5x5左上角在(0,0)中心点在(2,2)。同理终点通常也给的是中心点坐标。务必确认题目输入格式这是第一个易错点。注意2visited数组维度。这里第三维用0,1,2分别对应尺寸1,3,5。用尺寸索引比用时间更简单因为尺寸只有3种而时间可能很大。3.2 核心函数根据时间获取当前尺寸这是一个纯函数逻辑简单但必须绝对准确。static int getSize(int time) { if (time k) { return 5; // 下标2 } else if (time 2 * k) { return 3; // 下标1 } else { return 1; // 下标0 } }踩坑提醒边界条件。time k对应[0, k-1]时刻尺寸为5。time 2*k对应[k, 2k-1]时刻尺寸为3。这里最容易出错的是等号处理一定要根据题目描述反复确认。例如题目说“第k分钟时”还是胖的那么timek时尺寸应为5我们的条件time k就不对了需要改为time k。这是需要根据题目原文仔细核对的细节。3.3 碰撞检测判断移动/停留是否合法这是本题最核心、最容易写错的函数。它的作用是给定中心点坐标(cx, cy)和时间t判断以该点为中心、以size(t)为边长的正方形区域是否完全合法。static boolean check(int cx, int cy, int time) { int s getSize(time); // 计算正方形区域的左上角和右下角坐标 int half s / 2; // 对于尺寸5half2尺寸3half1尺寸1half0。 int top cx - half; int bottom cx half; int left cy - half; int right cy half; // 首先检查整个方块是否在迷宫范围内 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; }踩坑实录1半边长计算。对于尺寸s奇数从中心点(cx, cy)扩散的半边长是(s-1)/2。例如5x5中心点索引为2向上向左各覆盖2格向下向右各覆盖2格。所以half (s-1)/2。我上面代码中的s/2在Java整数除法下对于5得到2对于3得到1对于1得到0结果是正确的因为(5-1)/22。但为了逻辑更清晰我建议写成int half (s - 1) / 2;这样一眼就能看出意图。踩坑实录2边界遍历。for循环的边界是i bottom和j right一定要包含等于号否则会漏掉最下面一行和最右边一列的检查。踩坑实录3起点/终点合法性。在BFS初始化时需要检查起点在时间0是否合法。虽然题目数据通常保证起点是空地但严谨的代码应该加上检查。同理在BFS中每次从队列取出状态后如果要判断是否到达终点也应该用check(xe, ye, currentTime)验证一下终点在当前时间是否可到达虽然终点通常是空地但万一胖子太大终点周围有墙可能即使到了中心点身体却压着墙也算非法。这是一个很好的防御性编程习惯。3.4 BFS主框架实现有了上面的准备BFS的实现就相对模式化了。static int bfs(int sx, int sy, int ex, int ey) { QueueNode queue new LinkedList(); int startSizeIndex getSizeIndex(0); // 根据时间0获取尺寸索引 if (!check(sx, sy, 0)) { return -1; // 起点就不合法直接返回通常不会发生 } visited[sx][sy][startSizeIndex] true; queue.offer(new Node(sx, sy, 0)); while (!queue.isEmpty()) { Node cur queue.poll(); int x cur.x; int y cur.y; int t cur.time; // 终止条件到达终点且终点状态合法 if (x ex y ey) { // 虽然到达中心点还需确认此时胖子身体不压墙 if (check(ex, ey, t)) { return t; } // 如果不合法不能返回需要继续搜索例如等待变瘦后再抵达 } int currentSizeIndex getSizeIndex(t); // 操作1尝试向四个方向移动 for (int[] d : dirs) { int nx x d[0]; int ny y d[1]; int nt t 1; int newSizeIndex getSizeIndex(nt); // 剪枝1坐标越界 if (nx 0 || nx n || ny 0 || ny n) { continue; } // 剪枝2状态已访问 if (visited[nx][ny][newSizeIndex]) { continue; } // 剪枝3移动后新位置状态不合法碰撞检测 if (!check(nx, ny, nt)) { continue; } visited[nx][ny][newSizeIndex] true; queue.offer(new Node(nx, ny, nt)); } // 操作2尝试停留在原地等待 int nt_stay t 1; int newSizeIndex_stay getSizeIndex(nt_stay); // 停留也需要检查合法性因为变瘦后原来占的格子可能变成墙虽然罕见 if (!visited[x][y][newSizeIndex_stay] check(x, y, nt_stay)) { visited[x][y][newSizeIndex_stay] true; queue.offer(new Node(x, y, nt_stay)); } } return -1; // 队列为空仍未到达终点理论上不会发生因为可以无限等待 } // 辅助类存储状态 static class Node { int x, y, time; Node(int x, int y, int time) { this.x x; this.y y; this.time time; } } // 根据尺寸值返回visited数组的索引 static int getSizeIndex(int time) { int size getSize(time); if (size 1) return 0; else if (size 3) return 1; else return 2; // size 5 }核心技巧1停留操作的必要性。这是本题区别于普通迷宫BFS的关键。如果没有停留操作胖子在遇到狭窄通道时如果当前时间过不去他就没有“等待变瘦”这个选项算法会找不到解。停留和移动是并列的两种状态转移方式。核心技巧2去重策略的优化。上面的代码使用了visited[x][y][sizeIndex]。这里有一个潜在的优化点如果我们在时间t1以尺寸s1访问了(x,y)之后在更晚的时间t2以更小的尺寸s2s2 s1再次访问应不应该剪掉从最优性角度更晚的时间且尺寸更小似乎不如之前的状态。但更小的尺寸可能意味着能去往更多地方比如通过窄道。为了安全起见我们不做这个优化严格按尺寸索引去重即可状态数最多是n * n * 3完全在承受范围内。踩坑实录4时间与尺寸的同步。在check函数和getSizeIndex函数中传入的时间t必须是状态发生后的时间。例如从状态(x,y,t)移动到(nx,ny)移动这个动作花费了1单位时间所以检查新位置是否合法时使用的时间是t1对应的尺寸是getSize(t1)。这一点在逻辑上必须保持一致否则会导致错误的碰撞判定。4. 性能分析与测试用例设计4.1 时间复杂度分析BFS的状态数上界是O(n^2 * 3)因为每个格子最多在3种尺寸下被访问一次。每个状态会尝试4次移动和1次停留共5次扩展。每次扩展需要执行一次check函数而check函数需要遍历最多5x525个格子。因此最坏情况下的时间复杂度大约是O(5 * n^2 * 3 * 25) O(375 * n^2)对于题目中n在30左右的范围计算量非常小完全可行。4.2 构造测试用例与调试自己构造测试用例是debug和确保理解正确的关键。我通常会设计以下几类基础功能测试n5, k10迷宫全是.。起点(2,2)终点(2,2)。答案应为0。n5, k10迷宫全是.。起点(2,2)终点(2,3)。答案应为1直接移动。尺寸阻挡测试n7, k100 (意味着很长时间都是5x5) 迷宫 ....... ....... .... ...... .... ....... ....... 起点(2,2)终点(4,4)。中间是一个“回”字形墙通道宽度为1。在5x5尺寸下胖子无法通过任何通道。必须等待到时间k以后变成3x3甚至2k以后变成1x1才能通过。这个用例可以测试“停留”逻辑和尺寸变化逻辑。边界条件测试起点或终点紧贴迷宫边缘。检查check函数的边界判断是否正确。k0的情况。这意味着从一开始就是1x1退化为标准迷宫问题。k值很大但迷宫很小测试长时间等待的逻辑。复杂路径测试设计一个需要多次“等待-移动”交替的迷宫验证BFS能找到最优的时机选择。在调试时我最常用的方法是打印状态日志。在BFS循环中打印出每次从队列取出的状态(x, y, t, size)以及每次成功转移的新状态。通过观察状态扩展的顺序和visited数组的变化可以非常直观地发现逻辑错误比如该停留的时候没有停留或者碰撞检测算错了范围。5. 常见问题与优化策略延伸5.1 为什么BFS能保证找到最短时间因为我们将“等待”也视为一次代价为1的转移时间1。这样整个状态空间图就变成了一个边权全为1的无向图严格来说从状态A到状态B的转移是单向的因为时间不可逆。BFS在边权为1的图上第一次扩展到目标状态所经历的步数时间就是最短路径。5.2 能否用DFS或记忆化搜索理论上可以但不如BFS直观和高效。DFS需要处理循环访问状态依赖时间可能形成环和最优解判断实现起来更复杂。BFS的层序扩展特性天然适合求解最短步数问题。5.3 如果每步移动代价不同怎么办如果移动和停留的代价不同比如移动耗时2停留耗时1那么这就变成了边权不等的图需要使用Dijkstra算法优先队列BFS。状态设计和碰撞检测逻辑不变只是将队列换成优先队列小顶堆每次取出当前时间最小的状态进行扩展。5.4 一个易忽略的优化提前终止在BFS中当我们从队列取出一个状态如果发现当前时间t已经超过了某个已知的可行解时间比如通过简单估算得到的一个上界可以提前终止该分支的搜索。虽然在这道题中状态空间很小不需要但在更复杂的问题中这是一个有用的剪枝。5.5 关于visited数组的再讨论我们使用visited[x][y][sizeIndex]。有没有可能用visited[x][y][time]绝对不行因为time范围可能很大数组开不下。用尺寸索引是对状态空间的极大压缩这正是本题建模的巧妙之处。它抓住了问题的本质影响后续决策的不是具体时间而是时间所对应的“胖瘦”状态。6. 举一反三这类问题的通用解题框架“大胖子走迷宫”本质上是一类“带有状态依赖的网格图搜索”问题。它的解题框架可以总结如下识别核心变量除了坐标(x, y)还有什么因素直接影响移动的合法性本题是时间t通过尺寸影响。其他题目可能是剩余能量、持有钥匙状态、方向等。定义搜索状态将核心变量加入状态。例如(x, y, t)或(x, y, energy, keys)。设计状态转移分析从当前状态通过哪些“操作”能到达哪些新状态。操作通常包括移动、使用技能、等待等。每个操作都会改变状态变量如坐标、时间、能量。确定转移代价与搜索算法如果所有操作代价相同如都是1步用BFS。如果代价不同用Dijkstra。如果求所有路径或存在性可以用DFS记忆化。实现合法性检查根据新状态的所有变量判断这次转移是否被允许如是否撞墙、能量是否够用、时间是否满足条件。设计状态去重定义在什么情况下两个状态被认为是“相同的”从而可以剪枝。通常如果两个状态的(x,y)和所有影响未来决策的变量都相同则视为相同。本题中(x,y)和尺寸相同即视为相同状态因为相同尺寸下的后续可能性是一样的。把这个框架套用到其他题目比如“迷宫寻宝需要收集钥匙开门”、“吃豆人有能量时间限制”、“推箱子箱子状态”等你会发现它们都是这个框架的变体。掌握这个建模思想比死记硬背一道题的代码要重要得多。最后在实现这类题目时画图辅助思考极其重要。在纸上画出网格标出胖子的覆盖范围模拟他移动和等待的过程能帮你迅速理清边界条件和碰撞检测的逻辑避免陷入代码调试的泥潭。这道题代码量不大但思维密度很高非常适合用来训练将复杂问题抽象为规范搜索模型的能力。