“PTA L3-004 肿瘤诊断”是很多算法学习者绕不开的一道经典题。表面看只是个BFS，实际上结合了三维遍历、连通块统计、阈值过滤和大数据量处理，几层东西叠在一起，稍不留神就不是超时而是内存出问题。如果你只熟练二维岛屿问题，第一次写这个题十有八九要翻车。这篇我来拆一下题目的考点、三维BFS的设计思路、一个直接能AC的实现，以及我实际踩过的几个坑。

题目给的是一个三维网格：每张切片是M行N列，一共有L张切片，整体像个长方体，每个格子叫体素，存0或1。1代表病变组织，0代表正常组织，所有相邻的1构成一个三维连通区域，也就是一个肿瘤块，这个块里1的数量就是体积。但并不是所有小块都算，题目还会给一个阈值T，体积小于T的连通块被当作噪声忽略，只有体积不小于T的块才累加到答案里。最后的答案就是这些满足条件的块体积总和。

这套题目真正适合两类人：一是算法竞赛刚入门、想把BFS吃透的人；二是工程上要处理三维体数据、想理解连通域标记的人。两者的核心需求是一样的：怎么在几百万甚至上千万个体素上又快又稳地找出所有三维连通区域。

1. 题目在考什么：从CT切片到“体积阈值+连通块统计”

1.1 体素、邻接与体积的定义

先把题目翻译成代码语言。输入第一行是M、N、L、T，其中M是每一层切片的行数，N是每一层的列数，L是切片数量，T是体积阈值。接下来会有L个二维矩阵，每个矩阵大小是M×N，值只有0和1。

体素的邻接关系是这个题的关键。每个体素不是和八个邻居都相连，而是只连六个方向：

• 同一层内：上下左右四个邻居；
• 跨层：上一张切片同一坐标位置、下一张切片同一坐标位置。

也就是说，一个体素的邻居包括：

(x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)

其中x是行、y是列、z是层。少了任意一个方向，结果都会出错。最容易忘的是上下两层，这个在后面坑点部分还要专门说。

一个连通块里的所有1的个数就是它的体积。注意体积不是包围盒体积，也不是表面积，就是简单的“这个块里到底有多少个1”。某些题目会说“质量”“点数”，本质都一样。

1.2 规模估算决定了这道题不能随便写

我先把规模摆在前面，因为很多解法是不是可行，先看数据规模就知道。经典版本里M最大是1286，N最大是128，L最大是60。算一下总体素数：

1286 × 128 × 60 = 9,876,480

接近一千万。这个量级意味着：

• 三层嵌套vector存储图不是不行，但内存分配和访问开销较大；
• 递归DFS很容易爆栈，后面会细说；
• cin不关同步直接读一千万个整数，速度会非常难看；
• 每个体素存成int和存成char，内存差四倍。

所以这题的正确姿势基本是：静态数组存图、BFS、手写队列、输入输出上提速。它不是让你讨论“用DFS还是BFS更优雅”的题，而是让你在正确思路之上把工程细节也做对的题。

1.3 考点拆解

这题本质上就是“三维01网格中统计所有大小不小于T的连通分量大小之和”。拆成三部分：

• 三维遍历：要按照层、行、列的顺序处理L×M×N个点；
• 连通分量统计：从每个没访问过的1出发，向六个方向扩展；
• 阈值过滤：每个连通分量统计完后，体积达到T才计入最终答案。

看懂这个抽象，题目就没有悬念了，剩下的就是实现细节。这也是我对所有刷题者的建议：别急着写代码，先把“这题到底在求什么”用一句话概括出来。

2. 三维BFS的骨架设计：六方向遍历、队列与判重的取舍

2.1 为什么选BFS而不是DFS

只从算法角度说，DFS也能做连通块统计，递归写法甚至更短。但这题有个现实问题：一个连通块最多可能包含接近一千万个点，DFS递归深度也可能接近一千万层。普通编译器的调用栈根本扛不住，运行到一半就栈溢出。你可能会想“那我改成手写栈”，可以，但手写栈本质上和BFS的队列复杂度差不多，代码也没简洁到哪去。

BFS的好处是天然用循环加队列，不依赖系统调用栈。而且三维BFS这套模板后面还能直接迁移到三维最短路问题。所以这道题选BFS，不是因为它花哨，是因为它是大状态空间下最稳的解法。

2.2 坐标系与方向数组

我给坐标系的定义如下：

遍历顺序就用“先外层z，再中间x，最后内层y”，这样既好读又不容易出错。方向数组可以这样写：

int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1};

每轮循环里取第k个方向，新的坐标就是：

int nx = x + dx[k]; int ny = y + dy[k]; int nz = z + dz[k];

然后检查nz、nx、ny是否越界，以及img[nz][nx][ny]是不是1。是1就把它改成0并入队。

2.3 判重方案：直接用原数组当访问标记

二维岛屿问题里，常见做法是开一个visited二维数组，访问过就标记。三维一样可以开：

bool vis[MAXL][MAXM][MAXN];

但在这个题里，有个更省内存也更快的做法：因为题目最后只要统计体积，不需要保留原图，所以BFS过程中把访问过的1直接改成0。这样以后从外层循环再扫到这个点，它已经是0，不会重复统计。

这招带来的好处很实际：

• 省掉一整个visited数组的内存；
• 省掉一次对全图执行memset的初始化时间；
• 代码逻辑还更短。

前提只有一个：你不修改原始数据不影响最终答案。本题完全满足。

2.4 队列设计：坐标打包成一个int

很多第一次写三维BFS的人会定义这样一个结构体：

struct Node { int x, y, z; };

然后用STL的queue 。数据量小的时候没问题，但这个题最坏情况下一千万个点都可能入队。一个Node十二字节，一千万就是一百二十兆，加上图和系统开销，很容易摸到内存上限。

所以我推荐把三维坐标打包成一个int：

int id = (z * M + x) * N + y;

取出的时候再解包：

y = id % N; id /= N; x = id % M; z = id / M;

一千万个int大概四十兆，比Node队列小三分之二以上。缺点是多做几次整数除法和取模，但一千万量级完全扛得住，而且代码不复杂。

还有一个很小的点：BFS入队时就要把对应的img值改成0，而不是出队时再改。否则同一个点可能被入队很多次，队列大小会膨胀，甚至超过理论体素数。

3. 可以直接AC的实现与逐段代码解读

下面这个版本我没有加花哨的优化，优先保证逻辑清楚，同时兼顾了内存和速度。我用的是C++语法，所有关键点都做了注释。

#include <cstdio> const int MAXL = 62; const int MAXM = 1290; const int MAXN = 130; const int MAXV = MAXL * MAXM * MAXN; int M, N, L, T; char img[MAXL][MAXM][MAXN]; int q[MAXV]; int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; int bfs(int sz, int sx, int sy) { int head = 0, tail = 0; int cnt = 0; // 起点入队，同时立刻标记为0，防止重复入队 q[tail++] = (sz * M + sx) * N + sy; img[sz][sx][sy] = 0; while (head != tail) { int id = q[head++]; // 解码三维坐标 int y = id % N; id /= N; int x = id % M; int z = id / M; cnt++; for (int k = 0; k < 6; k++) { int nx = x + dx[k]; int ny = y + dy[k]; int nz = z + dz[k]; if (nx < 0 || nx >= M) continue; if (ny < 0 || ny >= N) continue; if (nz < 0 || nz >= L) continue; if (img[nz][nx][ny] == 0) continue; img[nz][nx][ny] = 0; q[tail++] = (nz * M + nx) * N + ny; } } return cnt; } int main() { scanf("%d%d%d%d", &M, &N, &L, &T); // 读入L层，每层M行，每行N个数 for (int z = 0; z < L; z++) { for (int x = 0; x < M; x++) { for (int y = 0; y < N; y++) { int v; scanf("%d", &v); img[z][x][y] = (char)v; } } } int ans = 0; for (int z = 0; z < L; z++) { for (int x = 0; x < M; x++) { for (int y = 0; y < N; y++) { if (img[z][x][y] == 1) { int cnt = bfs(z, x, y); if (cnt >= T) { ans += cnt; } } } } } printf("%d\n", ans); return 0; }

3.1 为什么图要用char不能用int

img这个三维数组我用的是char，不是int。原因很简单：里面只存0和1，一个字节就够。一千万个体素用char存差不多十兆，用int存就变四十兆。这个差距在大内存限制下也许不明显，但一旦内存给得紧，这就是能不能过的区别。

这样做有个连带问题：scanf不能直接把%d读进char变量。scanf("%d", &v)会向地址写四个字节，而char变量只有一字节，写多了会破坏相邻内存，造成非常诡异的错误。所以正确写法是先用int变量v接住，再手动转成char。

3.2 解码时先y后x再z的顺序

坐标打包和解包的顺序必须一致。打包是：

id = (z * M + x) * N + y;

所以解包就要反过来：

y = id % N; id /= N; x = id % M; z = id / M;

这里我常看到有人写成z = id / (M * N)，那是最外层的说法；因为我第二步已经把id除以N了，所以这里直接id / M就是z，别搞混。

3.3 主循环的扫描顺序

主循环用z、x、y三层嵌套，逐个检查img[z][x][y]是否为1。只要发现一个1，就说明这是一个新连通块，调用BFS把这个块所有点都清成0。因此外层循环不会重复统计同一块里的其他点。

这就是“原数组当访问标记”和“全局扫描”结合起来的完整流程。每次BFS返回这个块的体积cnt，只有当cnt >= T时才加到ans。阈值边界要格外注意：题目是“体积小于T的忽略”，等于T的必须算进去。

4. 复盘容易丢分的四个细节：边界、阈值、输入和内存

4.1 最大的隐性坑：把scanf直接读到char数组

这个问题我当年第一次写的时候就踩过。当时图省事，写成：

scanf("%d", &img[z][x][y]);

本地小数据跑起来没问题，一提交就各种内存错乱。原因上面说过了：%d按四字节写入，char只有一字节。看起来输入只有0和1没问题，但多出来的三个字节会覆盖相邻数组元素，导致整个图乱七八糟。排查起来非常痛苦，因为错误点和输入位置不在同一层，甚至不在同一片区域。

后来我把数组开成int，这个问题消失了，但内存从十兆变四十兆。再后来才改成先读int再赋值char的形式。这个写法在代码里就三行，但非常关键。

4.2 方向漏了上下层

二维BFS做多了，很容易在三维时只写四个方向。我自己第一次就是把dx、dy写得飞起，忘记加dz的两个方向。结果小样例看着对，一提交答案偏小。为什么？因为同一个肿瘤被上下层分隔成好几个小块，每个小块单独统计后，有的刚好小于T被丢掉，总体积就少算了。

检查方向数组有个笨但有效的方法：数一下，必须是六组。如果你用的是int dir[6][3]，就检查每一组三个分量是不是只有一个变化，且正负方向都齐了。

4.3 阈值是>=T，不是>T

题目说的是“体积小于T的块忽略”，那就意味着体积等于T的块不能忽略。很多代码写成：

if (cnt > T) ans += cnt;

这个bug在随机数据上很难发现，因为命中边界的情况很少，但测试点往往就盯这个边界。正确写法是cnt >= T。

还有一个和它类似的小坑：如果T给的是1，那相当于所有孤立点都算肿瘤，这没问题；但如果你把阈值逻辑反过来写，就很容易写错。建议在确认题面之前，不要凭感觉定是大于还是大于等于。

4.4 大数组放错位置

C/C++里在main函数内部开大数组，默认是往栈上放的。栈空间通常只有几兆到几十兆，一千万的数组放进去直接爆。这个题正确做法是把全局变量开在外面，或者至少加了static：

static char img[MAXL][MAXM][MAXN]; static int q[MAXV];

全局区和静态区没有栈那么紧张。写完代码以后看一眼变量定义位置，能省很多崩溃的排查时间。

4.5 输入输出速度

在数据量接近一千万的题里，cin不关同步是很危险的。即使只读不写，也会比scanf慢不少。如果你习惯用C++流，记得在main开头加：

ios::sync_with_stdio(false); cin.tie(0);

但我的建议是直接用scanf和printf，代码更朴素，也不会因为忘记关同步而踩坑。这题输出就一个整数，不需要构造大量输出，重点放在输入读取上。

5. 三维BFS的通用化：同一套思路还能迁移到哪些场景

5.1 三维最短路

三维BFS最常见的一个变体是三维迷宫最短路。状态空间还是三维网格，只不过每个点存的是“从起点到当前点的最短步数”。BFS天然按层扩展，所以第一次到达某个点时记录的步数就是最短步数。

迁移时只需要在队列节点里多加一个distance，或者用另一个三维数组存距离。初始化距离数组为-1，起点为0，每扩展一步就在原距离基础上加1。方向数组、越界判断、判重逻辑几乎原封不动。

5.2 状态不仅仅是三维坐标时怎么办

有些三维搜索题，每个状态除了坐标还有额外信息，比如“剩余步数”“朝向”“已收集物品”。这时候队列元素就不能只打包一个int了，需要定义结构体。但搜索骨架不变：入队时标记状态，出队时按状态转移，转移方向由题目定义的邻接关系决定。

核心能力其实就三点：

• 状态空间设计：哪些信息必须进队列；
• 状态转移：从当前状态能到哪些合法状态；
• 判重：哪些状态已经访问过。

只要你把这三件事想清楚，不管是三维BFS、三维最短路还是状态压缩广搜，本质都一样。

5.3 从这道题延伸出来的思考

L3-004的难点不在算法本身，而在它把“算法正确”和“工程细节”压在同一道题里考。你要同时处理好图存储、队列容量、判重时机、边界判断、输入性能和阈值逻辑。任何一环做得不彻底，都可能让人在某一组测试点上功亏一篑。

以我自己的经历来说，起初写这题版本时图省事，用三层vector套了一个DFS，思路完全对，提交却又是超时又是内存问题。后来改成静态char数组、手动队列、入队即置0、坐标打包，一遍通过。这个优化过程本身比题目更有价值，它逼着我去想数据到底怎么存、内存到底怎么涨。三维搜索后续还会碰到，但这个“先估算状态规模再设计存储结构”的习惯，自从写了这题之后我再也没丢过。