# L3-004. 肿瘤诊断

```3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0```

`26`

```// <!! dfs 搜索，最后两个测试点段错误，应该是递归层数太深爆栈了 !!>
#include <iostream>
using namespace std;

int m, n, l, t;
int area[65][1300][130];
bool visit[65][1300][130];
// 一个坐标点的立体周围 6 个方向: z, x, y
int directions[6][3] = {{0, -1, 0}, {0, 1, 0}, {0, 0, -1},
{0, 0, 1}, {1, 0, 0}, {-1, 0, 0}};

int dfs(int z, int x, int y) {
int res = 0;
if (z < 0 || z >= l || x < 0 || x >= m || y < 0 || y >= n ||
!area[z][x][y] || visit[z][x][y]) {
return res;
}
res++;
visit[z][x][y] = true;
int nextZ, nextX, nextY;
for (int i = 0; i < 6; i++) {
nextZ = z + directions[i][0];
nextX = x + directions[i][1];
nextY = y + directions[i][2];
res += dfs(nextZ, nextX, nextY);
}
return res;

}

int main() {
cin >> m >> n >> l >> t;
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
scanf("%d", area[i][j] + k);
}
}
}
int res = 0;
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
if (area[i][j][k] && !visit[i][j][k]) {
int currentRes = dfs(i, j, k);
if (currentRes >= t) {
res += currentRes;
}
}
}
}
}

cout << res << endl;

return 0;
}```

```// <!! 单平面 dfs + 层数循环，dfs 倒是不爆栈，但是最后一个测试点谜之答案错误。。。!!>
#include <iostream>
#include <vector>
using namespace std;

typedef struct Point {
Point(int r, int c) {
row = r, col = c;
}
int row;
int col;
} Point;

int m, n, l, t;
int area[65][1300][130];
bool visit[65][1300][130];
vector<Point> points;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

int dfs(int a[][130], bool visit[][130], int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || visit[r][c] || !a[r][c]) {
return 0;
}
int res = 1;
points.push_back(Point(r, c));
visit[r][c] = true;
int nextR, nextC;
for (int i = 0; i < 4; i++) {
nextR = r + directions[i][0];
nextC = c + directions[i][1];
res += dfs(a, visit, nextR, nextC);
}
return res;
}

int getVolume() {
int res = 0;
// 这个循环的含义是：获取从第 i 层平面到最顶层平面的所有体积不小于阀值的肿瘤块的体积。
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
if (area[i][j][k] == 1 && !visit[i][j][k]) {
int currentRes = 0;
points.clear();
// 储存当前平面搜索的结果
currentRes += dfs(area[i], visit[i], j, k);
vector<Point> v = points;
// 向上层遍历
for (int ii = i+1; ii < l; ii++) {
points.clear();
// 如果下一层没有找到肿瘤点，那么这块肿瘤体积已经确定
if (v.size() == 0) {
break;
}
// 遍历当前层所有和下层相同坐标的点，查找肿瘤点
for (int jj = 0; jj < v.size(); jj++) {
if (area[ii][v[jj].row][v[jj].col] &&
!visit[ii][v[jj].row][v[jj].col]) {
currentRes += dfs(area[ii], visit[ii], v[jj].row, v[jj].col);
}
}
v = points;
}
// 比较肿瘤体积阀值决定是否保存该肿瘤块体积
if (currentRes >= t) {
res += currentRes;
}
}
}
}
}
return res;
}

int main() {
cin >> m >> n >> l >> t;
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
scanf("%d", area[i][j] + k);
}
}
}

cout << getVolume() << endl;

return 0;
} ```

```// 最后 bfs
#include <iostream>
#include <queue>
using namespace std;

typedef struct Point {
Point(int zz, int xx, int yy):z(zz), x(xx), y(yy) {}
int z;
int x;
int y;
} Point;
int m, n, l, t;
int area[65][1300][130];
bool visit[65][1300][130];
// 一个坐标点的立体周围 6 个方向: z, x, y
int directions[6][3] = {{0, -1, 0}, {0, 1, 0}, {0, 0, -1},
{0, 0, 1}, {1, 0, 0}, {-1, 0, 0}};

int bfs(int z, int x, int y) {
int res = 0;
if (z < 0 || z >= l || x < 0 || x >= m || y < 0 || y >= n ||
!area[z][x][y] || visit[z][x][y]) {
return res;
}
queue<Point> points;
points.push(Point(z, x, y));
visit[z][x][y] = true;
int nextZ, nextX, nextY;
while (!points.empty()) {
Point p = points.front();
points.pop();
res++;
for (int i = 0; i < 6; i++) {
nextZ = p.z + directions[i][0];
nextX = p.x + directions[i][1];
nextY = p.y + directions[i][2];
if (nextZ < 0 || nextZ >= l || nextX < 0 || nextX >= m || nextY < 0 || nextY >= n ||
!area[nextZ][nextX][nextY] || visit[nextZ][nextX][nextY]) {
continue;
}

visit[nextZ][nextX][nextY] = true;
points.push(Point(nextZ, nextX, nextY));
}
}
return res;
}

int main() {
cin >> m >> n >> l >> t;
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
scanf("%d", area[i][j] + k);
}
}
}
int res = 0;
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
if (area[i][j][k] && !visit[i][j][k]) {
int currentRes = bfs(i, j, k);
if (currentRes >= t) {
res += currentRes;
}
}
}
}
}

cout << res << endl;

return 0;
}```

0 条评论

• ### 2018 团队设计天梯赛题解---华山论剑组

2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛，如果团队平均水平不高的话，单凭一个人，分再高也很难拉起来（当然，一个人...

• ### 查找算法

查找，作为应用最为广泛和最基础的算法思想之一，几乎在所有应用程序之中都有它的思想身影。往细一点说：查找可以有 顺序查找、二分查找、散列表查找，下面依次来看一下这...

• ### 八大经典排序算法总结

终于到了排序部分了。这部分也是最难总结的，毕竟不同的排序算法思想多少会有差别，有些甚至完全不一样。今天不知道要码多少字。好吧，先为我的手指默哀三分钟~

• ### LeetCode Contest 166

但是在用c++的快排的时候，被坑了，我一直的习惯是写自定义比较函数，没有写运算符重载，不知道为什么一直RE，浪费了挺多时间

• ### 3117 高精度乘法

3117 高精度练习之乘法  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给出...

• ### 浙大版《C语言程序设计（第3版）》题目集 习题5-4 使用函数求素数和

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题4-6 水仙花数

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

• ### 10:Challenge 3（树状数组直接修改）

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列，有M次操作，每次操作是以下两种之一： （1）...

• ### Day2上午解题报告

预计分数：100+0+60=160 实际分数：100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

• ### P3808 【模版】AC自动机（简单版）

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。 题目描述 给定n个模...