后台常有人问我 L3 的题到底从哪道开始刷比较合适我给的答案里一般都会提到这道PTA L3-004 肿瘤诊断。它看起来就是“二维BFS加一个维度”但真要把它拿下你会同时撞上三维连通性、千万级数据、内存紧张、阈值过滤这些此前很少一起出现的考点。我见过不少二维BFS写得很顺的同学到这一题照样栽在数组下标和队列实现上。这篇文章按我实际做题的次序来从题意、数据存储、BFS 实现到典型翻车现场完整带一遍。如果你正准备考 PAT/PTA或者刚学完 BFS 想找个进阶练习题这一篇可以直接照着刷。1. 先把题目翻译成人话1.1 三维体素里的连通块计数题目给的不是一张图而是 L 张切片组成的立体数据。想象一下把一整块组织切成很多薄片每张切片上有一个 M 行 N 列的二维矩阵矩阵里只有 0 和 11 就代表这个位置有肿瘤细胞0 代表正常组织。把这些切片按顺序叠起来就得到一个三维的“体素”空间。你需要做的是找出所有由相邻的肿瘤体素组成的连通块。这里的“相邻”是三维意义上的相邻同一个切片里上下左右四个方向以及相邻切片之间正上方、正下方两个方向合起来一共六个方向。这和二维迷宫只有 4 个方向不一样很多新手一上来就漏掉“层与层之间”这两个方向。1.2 为什么要做阈值过滤光找连通块还不够题目还加了一个条件只把体积不小于某个阈值的连通块计入最终答案。这个设计其实很贴近医学影像的实际场景。CT 切片扫描时会产生不少噪声单独一个点的亮区或几个像素连成的碎点大概率不是真正的病灶。你如果不过滤把这些噪声全算进去最后统计出来的体积就会严重偏高。所以题目要求你先把连通块整个找出来数出这个块里到底有多少个 1然后和阈值 T 比较。体积够了才累加不够就当成噪声扔掉。也就是说“连通块体积”是中间产物“最终答案”是所有合格块体积之和这个转换非常容易在做题时漏掉。1.3 数据规模决定了写法上限原题很清楚给出了范围约束切片数 L 不超过 60每张切片行数 M 不超过 1286列数 N 不超过 128。算一下总格数60 × 1286 × 128 ≈ 988 万接近一千万个格子。这个规模决定了你不能用递归深度很大的写法也不能随意开一个很大的 vector 嵌套结构更不能用 O(N²) 或更高复杂度的算法去处理连通块。线性扫描一遍是必须的而且还不能线性扫得太奢侈。2. 为什么这道题非用 BFS 不可2.1 递归 DFS 在极端数据下会直接炸栈一开始很多人会想连通块嘛DFS 也能做。确实DFS 逻辑更简单写起来甚至比 BFS 少几行代码。但问题在于这里最坏情况是什么整个三维矩阵可能全部是 1也就是说存在一个接近一千万格子的超大连通块。如果你用 DFS 递归去遍历递归深度会达到连通块大小级别。哪怕评测栈空间给到几十 MB这种深度也远远超出安全范围。有人可能会说那我不用系统栈自己开个栈模拟 DFS 行不行行但手写栈去模拟递归状态尤其是三维坐标压栈压入状态写起来比 BFS 队列复杂得多。相比之下BFS 使用的队列天然避免了递归深度问题。2.2 BFS 的复杂度和内存占用都非常理想BFS 的核心保证是每个格子最多入队一次。全图九百万格子的情况下每个格子的邻居检查次数是常数级别整体复杂度 O(L × M × N)也就是线性扫一遍在评测环境下完全跑得动。从内存角度说BFS 只需要保留一层的边界节点最坏情况下队列也不会超过总格点数。这个特性对千万级数据很关键后面我会专门讲队列实现。这里还要顺带说一句并查集其实也能做这题。把相邻的 1 全部 union 起来最后遍历所有根节点统计块大小。但并查集需要一个额外的父节点数组九百万的 int 数组又要多占近 40 MB而且 union 次数多、find 的路径压缩操作也带来额外开销。除非你对并查集特别熟否则在这种题里它不如 BFS 直接。3. 千万级数据的内存设计是真正的分水岭3.1 先算一笔内存账很多二维 BFS 写习惯的同学会下意识地声明int mp[100][100]这样的二维数组这题一上来就很不适应三维数组至少长这样a[60][1286][128]。如果你用int存这个数组的大小是60 × 1286 × 128 × 4 字节 39,517,440 字节 ≈ 39.5 MB。这是原数组本身。如果你再开一个bool vis[60][1286][128]做访问标记又要多近 10 MB。如果再用 STL 的queue去存一堆坐标结构体你的内存峰值会很难看。评测环境内存限制一般是百兆级别并不代表你可以随便浪费。3.2 原数组本身就可以当访问标记有一个几乎零成本的优化思路你不需要额外开 vis 数组访问过的肿瘤体素直接在原数组里改成 0。这样做的原理很简单。我们在扫描全图时每遇到一个 1就把它作为起点做一次 BFS把这一整块连通区域全部找到。找到之后这个连通块里所有格子在这个三维矩阵里就不再需要被保留了因为它们在后续扫描中不会被再次用到。把它们改成 0相当于把它们标记成“已访问”。之后主循环扫描到它们时会当成正常组织跳过。这种做法简洁且高效。如果担心修改原数据会有什么副作用这道题完全不用担心因为你只统计一次后面不会再依赖这些数据。3.3 手写队列比 STL queue 更值得选STL 的队列好不好用好用但对这种千万级数据量我们得考虑两个问题一是内存分配二是运行效率。std::queue底层默认用 deque 实现会按块分配内存在大量 push 的场景下速度还不错但内存占用不一定小。更重要的是如果用queuepairint,int或者结构体node{x,y,z}每个节点如果占 12~16 字节队列峰值一旦到百万甚至千万额外内存就很可观了。推荐做法是手写数组模拟队列而且直接把三维坐标压成一维编号来存int id (x * M y) * N z;然后队列元素只存这个 int。取出的时候再把一维编号反解成三维坐标int x id / (M * N); int y (id / N) % M; int z id % N;这样每个队列元素只占 4 字节整个队列最多需要九百万个 int 空间约 40 MB非常可控。如果你觉得反解除法运算会影响速度那是多虑了。九百万次除法在现代评测机上消耗很小完全在可接受范围内。3.4 用 char 数组再省 30 MB存储原矩阵时还有一个很大的优化空间int是 4 字节但我们只需要存 0 和 1用char一个字节就够了。把三维数组声明成char a[60][1286][128]整个矩阵只需要约 9.4 MB。两个方案对比一下存储方案原数组内存额外访问标记队列峰值估算综合推荐度int 原数组 STL 队列39.5 MB无改原数据偏高小数据可以大测试点不稳int 原数组 手写一维队列39.5 MB无改原数据约 40 MB基本能过char 原数组 手写一维队列9.4 MB无改原数据约 40 MB推荐char 原数组 bool vis STL 队列9.4 MB约 9.8 MB偏高不推荐用char数组还有个额外好处CPU 读取一个字节比读取一个 4 字节 int 要更省缓存空间对于九百万格子的连续扫描有一定收益。4. 完整实现方向数组、BFS 主过程与可运行代码4.1 先约定坐标含义我建议直接把三维数组定义成a[x][y][z]其中 x 对应切片层号范围 0 到 L-1y 对应切片内行号范围 0 到 M-1z 对应列号范围 0 到 N-1。六个方向对应x 方向上一层、下一层y 方向同一层内上边、下边z 方向同一层内左边、右边方向数组可以写成这样int dx[6] {0, 0, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, 0, 0}; int dz[6] {1, -1, 0, 0, 0, 0};注意这里顺序很容易写乱。我习惯先想清楚“每个维度有几对方向”x 方向一对y 方向一对z 方向一对加起来 6 个。写完后最好在代码里加个注释标清楚哪两个是切片方向、哪两个是行方向、哪两个是列方向。4.2 核心 BFS 过程BFS 的骨架很固定。以某个起点开始把它入队并立刻把原数组的 1 改成 0然后不断从队列头部取出节点计数器加一再检查六个方向的邻居。只要邻居还在边界内并且值为 1就将它入队并修改值。这里面有一个非常关键的细节入队时立即标记而不是出队时再标记。如果等到出队时才把格子改成 0那么同一个格子可能被多个邻居重复入队队列里会出现大量重复元素既浪费内存还可能让计数出错。这个错误非常隐蔽二维 BFS 里很多人就踩过三维场景下更明显。4.3 可运行的 C 参考代码#include cstdio using namespace std; const int MAXL 60; const int MAXM 1286; const int MAXN 128; char a[MAXL][MAXM][MAXN]; // 只存 0/1节省内存 int dx[6] {0, 0, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, 0, 0}; int dz[6] {1, -1, 0, 0, 0, 0}; int L, M, N, T; const int MAXQ MAXL * MAXM * MAXN 5; int q[MAXQ]; // 存一维编号 int bfs(int sx, int sy, int sz) { int head 0, tail 0; int id (sx * M sy) * N sz; q[tail] id; a[sx][sy][sz] 0; // 入队即标记 int cnt 0; while (head tail) { id q[head]; int x id / (M * N); int y (id / N) % M; int z id % N; cnt; for (int i 0; i 6; i) { int nx x dx[i]; int ny y dy[i]; int nz z dz[i]; if (nx 0 || nx L || ny 0 || ny M || nz 0 || nz N) { continue; } if (a[nx][ny][nz] 1) { a[nx][ny][nz] 0; q[tail] (nx * M ny) * N nz; } } } return cnt; } int main() { scanf(%d%d%d%d, L, M, N, T); for (int x 0; x L; x) { for (int y 0; y M; y) { for (int z 0; z N; z) { int tmp; scanf(%d, tmp); a[x][y][z] (char)tmp; } } } int ans 0; for (int x 0; x L; x) { for (int y 0; y M; y) { for (int z 0; z N; z) { if (a[x][y][z] 1) { int vol bfs(x, y, z); if (vol T) { ans vol; } } } } } printf(%d\n, ans); return 0; }4.4 主循环为什么也必须是三维全扫描代码最后有一个三层循环从最底层切片一直扫到最顶层切片。每遇到 1 就把它当成一个连通块的起点调用一次 BFS。因为 BFS 内部会把整个连通块全部置 0所以主循环不会重复处理同一个块。注意这里主循环的顺序无所谓但你必须保证三次循环完整覆盖所有切片、所有行、所有列。有人把层数和行数搞反写成for (int x 0; x M; x) for (int y 0; y L; y)虽然局部变量名看着没问题实际访问数组时就把两个维度调换位置读入和 BFS 全部乱套。5. 实战踩坑考场上最容易翻车的几个点5.1 方向数写错二维习惯是最强干扰从二维 BFS 迁移到三维 BFS最大的坑就是方向数组。二维只需要上下左右四个方向很多人把头两个三维方向数组写成了四个结果层与层之间的“穿越”完全没有处理连通块被拆得七零八落答案明显偏小。我的自查方法很简单写完之后数一下方向数组里的元素个数。必须是 6 个不是 4 个也不是 8 个。三维空间中的面相邻就是 6 个方向不需要处理对角线。5.2 入队时标记和出队时标记差别有多大拿一个最简单的二维例子做类比假设当前你在 (0,0)它的两个邻居 (1,0) 和 (0,1) 都指向同一个格子 (1,1)。如果入队时就把格子标记那么 (1,1) 只会被第一个找到它的邻居入队一次。如果出队时才标记(1,1) 就会同时被两个邻居当作合法邻居入队两次。二维已经如此三维比二维邻居更多重复入队的概率更大。重复入队会造成什么结果轻则队列膨胀、运行变慢重则同一块区域被重复计数体积统计完全失真。所以务必记住在入队的一瞬间完成标记。5.3 阈值判断放错位置一个连通块的所有格子是否要被统计取决于整块体积而不是遍历过程中逐个判断。正确做法是 BFS 完整跑完得到 cnt再与 T 比较。有人图省事在 BFS 内部每找到一个格子就判断一次或者根本不管阈值直接累加这两个错误都会导致最终答案不符合要求。我的习惯是把 BFS 返回值当成一个独立的“连通块体积”外部统一做if (vol T)判断。这样思路清楚也不容易漏。5.4 输入里的空行会导致读入错乱吗题目输入量很大切片与切片之间可能存在空行。看到空行的第一反应可能是“我要用 getline 逐行处理”。千万不要这样。直接把所有数字用scanf(%d, tmp)读取scanf会跳过所有空白字符包括换行和空格。用getline反而容易踩坑因为你必须手工去处理每一行边界、暂停读取、跳过空行等逻辑等于给自己挖坑。遇到这类海量数字输入最稳的方式就是无脑scanf。5.5 队列数组大小要按总格数来开手写队列int q[MAXQ]时MAXQ 我习惯取总格数再加一点余量。为什么因为一个连通块最大就是整个三维空间全部格子都可能是同一个块的一部分队列的 tail 下标理论上最多增长到总格数附近。即使 BFS 过程中同时存在的节点不会这么多但尾指针不复位的情况下依然需要这么大空间。如果你只开了一个普通大小比如 100000 的队列遇到最大测试数据直接越界评测结果往往不是超时而是运行时错误。5.6 快速自查清单做完整套代码之后提交前可以用这个清单快速检查一遍原数组声明是不是三个维度都按最大范围开了。方向数组是不是 6 个并且每一对方向都在正确的维度上。入队时有没有立刻把值改为 0。BFS 边界检查是否覆盖了层、行、列三个方向。主循环是不是完整遍历了 L × M × N 个格子。最终累加时有没有先和阈值 T 做比较。6. 还能不能接着优化从过题到写得更漂亮6.1 一维线性数组的终极形态如果你对上面这个版本已经非常熟可以再往前一步把整个三维数组映射成一维线性数组。比如char a[MAXL * MAXM * MAXN];访问某个位置时用pos (x * M y) * N z访问相邻位置只需要对 pos 做加减。但这时需要特别注意边界行尾的 pos 加 1 会跑到下一行的行首所以仍然需要额外判断 y、z 的边界条件。这个写法省掉一维数组嵌套代码更隐晦一般不建议在考试时冒险我平时也就看看而已。6.2 并查集方案要不要掌握有些参考书会给你并查集的解法。并查集确实是一个通用做法把相邻且都为 1 的位置合入同一集合之后统计每个根节点所在集合的体积。但它在这种题里并没有明显优势主要问题在于三维数组很大父节点数组又是一笔内存加上路径压缩的递归和循环代码量并不比 BFS 短。我认为你只要理解它的思路即可考试时优先用 BFS。6.3 什么时候不需要优化如果你的目标是“能过题”那么 char 数组加手写队列这个组合已经非常充足。如果你的目标是“先能把这道题做出来”那甚至直接用 int 数组加 STL queue 先跑通小数据也没关系理解算法优先级最高。我之前给朋友讲这题时总说先想清楚三个维度怎么存、六个方向怎么走再去碰那些花式优化。数据结构和 BFS 主逻辑没问题了内存优化其实就几行代码的事。7. 打通这题之后再看 BFS 会有种降维感我个人做完这道题之后回头看二维 BFS最大的感受是“原来 BFS 能在大规模数据下这么有讲究”。这道题本身并不需要什么高级算法但它强迫你同时处理维度扩展、边界条件、内存控制和统计口径。L3 系列里有很多题考的是思维深度但 L3-004 这类题考的是基本功是否真的扎实——三维来说数组开好、方向写对、队列控住你基本就赢了。最后再分享一个经验动手写三维网格类题目前先在草稿纸上画一个很小的小立方体把坐标轴方向和数组维度写清楚再开始写代码。这个习惯帮我少改了非常多次下标错误你也可以试试。