企业官网建设流程全解析

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

最近在复盘蓝桥杯的经典题目，翻到了第十届国赛Java B组的第8题——“大胖子走迷宫”。这题目名字起得挺有意思，一听就不是普通的迷宫寻路。普通的迷宫题，角色通常是一个点，上下左右移动，避开墙就行。但“大胖子”意味着角色有体积，不是点，而是一个占据多个格子的“方块”。这就让问题一下子复杂起来了：胖子在狭窄的通道里怎么转身？怎么判断会不会卡住？什么时候能“瘦下来”通过更窄的路？

这其实是一个典型的网格图上的状态搜索（BFS/DFS）问题，但引入了时间维度和角色尺寸变化这两个关键变量。它考察的不仅仅是基础的图遍历算法，更是对状态定义、边界条件处理和模拟能力的综合运用。很多同学初次接触时，容易用普通BFS去套，结果要么漏解，要么超时，根本原因就在于没有把“胖子”这个核心约束条件建模到搜索状态里。

我自己在实现和教学过程中，发现这道题有几个非常经典的“坑点”：一是对“占据”多个格子的碰撞检测逻辑容易写错；二是对“随时间变瘦”这个动态规则的理解和实现；三是BFS中状态去重的关键。接下来，我就结合这道题的典型数据，把从问题分析、思路构建、代码实现到调试优化的完整过程拆解一遍，并分享一些我踩过的坑和总结的技巧。

2. 问题核心与建模思路拆解

2.1 题目场景还原与约束分析

我们先抛开代码，把题目描述用更工程化的语言翻译一遍。题目通常会给一个n x n的字符矩阵表示迷宫，‘+’表示墙（障碍物），‘.’表示空地。一个“大胖子”小明，初始时非常胖，横向和纵向都占据了5个格子（即一个5x5的方块）。他每移动一步需要1单位时间。同时，他有一个神奇的技能：随着时间的推移，他会变瘦。具体规则是：从第0分钟开始，到第k分钟（含），他是5x5的大小；从第k+1分钟开始，到第2k分钟（含），他会变成3x3的大小；从第2k+1分钟开始及以后，他会恢复成正常的1x1大小（即一个点）。这里的k是题目给定的参数。

目标是找到小明从起点(xs, ys)走到终点(xe, ye)的最短时间。他只能上下左右移动，每次移动一格（以他中心点的移动为准）。移动的前提是：在移动完成后的那个时间点，他身体所占据的所有格子都必须在迷宫范围内，且都不是墙。

这里的关键约束有三个：

1. 动态尺寸：胖子的尺寸是随时间变化的函数size(t)。
2. 碰撞检测：移动是否合法，需要检查目标位置为中心、当前尺寸为边长的正方形区域内所有格子。
3. 状态依赖时间：能否从一个点移动到其相邻点，不仅取决于这两个点的位置，还取决于到达新点的时间，因为时间决定了你此刻的胖瘦，从而决定了这次移动是否合法。

2.2 为什么不能用普通BFS？

普通的BFS求迷宫最短路，状态就是坐标(x, y)，用一个visited[x][y] = true记录是否访问过。因为对于无权图（每一步代价为1），第一次访问某个点的距离就是最短距离。

但在这个问题里，这个性质被破坏了。原因在于，从不同路径、在不同时间到达同一个坐标(x, y)，其后续的可达性可能是不同的。举个例子：有一条狭窄的通道，宽度为1格。如果你在时间t=5（此时你还是5x5的胖子）到达通道口的格子A，你无法进入通道。但如果你在A点等待到时间t=10（此时你已变成1x1的瘦子），你就可以进去了。如果你用普通BFS，在t=5第一次访问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)可以转移到哪些新状态？

1. 移动：向上下左右四个方向移动一格，得到新坐标(nx, ny)，新时间t+1。转移的前提是：在时间t+1，以(nx, ny)为中心，以size(t+1)为边长的正方形区域内，所有格子合法。
2. 停留：停留在原地，时间t+1。这对应了“等待变瘦”的策略。转移前提是：在时间t+1，以(x, y)为中心，以size(t+1)为边长的正方形区域内，所有格子合法。注意，停留也需要检查合法性，因为随着你变瘦，你之前占据的某些格子可能已经是墙（虽然通常起点和空地不会），但严谨起见需要检查。

去重与剪枝：我们需要一个visited[x][y][s]数组来记录状态是否被访问过。这里s是尺寸（1，3，5）。因为时间可能很大，但尺寸只有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)。同理，终点通常也给的是中心点坐标。务必确认题目输入格式，这是第一个易错点。

注意2：visited数组维度。这里第三维用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分钟时”还是胖的，那么time=k时尺寸应为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; // 对于尺寸5，half=2；尺寸3，half=1；尺寸1，half=0。 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)/2=2。但为了逻辑更清晰，我建议写成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) { Queue<Node> 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以更小的尺寸s2（s2 < s1）再次访问，应不应该剪掉？从最优性角度，更晚的时间且尺寸更小，似乎不如之前的状态。但更小的尺寸可能意味着能去往更多地方（比如通过窄道）。为了安全起见，我们不做这个优化，严格按尺寸索引去重即可，状态数最多是n * n * 3，完全在承受范围内。

踩坑实录4：时间与尺寸的同步。在check函数和getSizeIndex函数中，传入的时间t必须是状态发生后的时间。例如，从状态(x,y,t)移动到(nx,ny)，移动这个动作花费了1单位时间，所以检查新位置是否合法时，使用的时间是t+1，对应的尺寸是getSize(t+1)。这一点在逻辑上必须保持一致，否则会导致错误的碰撞判定。

4. 性能分析与测试用例设计

4.1 时间复杂度分析

BFS的状态数上界是O(n^2 * 3)，因为每个格子最多在3种尺寸下被访问一次。每个状态会尝试4次移动和1次停留，共5次扩展。每次扩展需要执行一次check函数，而check函数需要遍历最多5x5=25个格子。因此，最坏情况下的时间复杂度大约是O(5 * n^2 * 3 * 25) = O(375 * n^2)，对于题目中n在30左右的范围，计算量非常小，完全可行。

4.2 构造测试用例与调试

自己构造测试用例是debug和确保理解正确的关键。我通常会设计以下几类：

1. 基础功能测试：

   • n=5, k=10，迷宫全是.。起点(2,2)，终点(2,2)。答案应为0。
   • n=5, k=10，迷宫全是.。起点(2,2)，终点(2,3)。答案应为1（直接移动）。

2. 尺寸阻挡测试：

   n=7, k=100 (意味着很长时间都是5x5) 迷宫： ....... ....... ..+++.. ..+..+.. ..+++.. ....... ....... 起点(2,2)，终点(4,4)。

   中间是一个“回”字形墙，通道宽度为1。在5x5尺寸下，胖子无法通过任何通道。必须等待到时间k以后变成3x3，甚至2k以后变成1x1才能通过。这个用例可以测试“停留”逻辑和尺寸变化逻辑。

3. 边界条件测试：

   • 起点或终点紧贴迷宫边缘。检查check函数的边界判断是否正确。
   • k=0的情况。这意味着从一开始就是1x1，退化为标准迷宫问题。
   • k值很大，但迷宫很小，测试长时间等待的逻辑。

4. 复杂路径测试：设计一个需要多次“等待-移动”交替的迷宫，验证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. 举一反三：这类问题的通用解题框架

“大胖子走迷宫”本质上是一类“带有状态依赖的网格图搜索”问题。它的解题框架可以总结如下：

1. 识别核心变量：除了坐标(x, y)，还有什么因素直接影响移动的合法性？本题是时间t（通过尺寸影响）。其他题目可能是剩余能量、持有钥匙状态、方向等。
2. 定义搜索状态：将核心变量加入状态。例如(x, y, t)或(x, y, energy, keys)。
3. 设计状态转移：分析从当前状态，通过哪些“操作”能到达哪些新状态。操作通常包括移动、使用技能、等待等。每个操作都会改变状态变量（如坐标、时间、能量）。
4. 确定转移代价与搜索算法：如果所有操作代价相同（如都是1步），用BFS。如果代价不同，用Dijkstra。如果求所有路径或存在性，可以用DFS+记忆化。
5. 实现合法性检查：根据新状态的所有变量，判断这次转移是否被允许（如是否撞墙、能量是否够用、时间是否满足条件）。
6. 设计状态去重：定义在什么情况下两个状态被认为是“相同的”，从而可以剪枝。通常，如果两个状态的(x,y)和所有影响未来决策的变量都相同，则视为相同。本题中，(x,y)和尺寸相同即视为相同状态，因为相同尺寸下的后续可能性是一样的。

把这个框架套用到其他题目，比如“迷宫寻宝（需要收集钥匙开门）”、“吃豆人（有能量时间限制）”、“推箱子（箱子状态）”等，你会发现它们都是这个框架的变体。掌握这个建模思想，比死记硬背一道题的代码要重要得多。

最后，在实现这类题目时，画图辅助思考极其重要。在纸上画出网格，标出胖子的覆盖范围，模拟他移动和等待的过程，能帮你迅速理清边界条件和碰撞检测的逻辑，避免陷入代码调试的泥潭。这道题代码量不大，但思维密度很高，非常适合用来训练将复杂问题抽象为规范搜索模型的能力。