专栏首页指点的专栏L3-004. 肿瘤诊断

L3-004. 肿瘤诊断

L3-004. 肿瘤诊断

题目链接

在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

输入格式:

输入第一行给出4个正整数:M、N、L、T,其中M和N是每张切片的尺寸(即每张切片是一个M×N的像素矩阵。最大分辨率是1286×128);L(<=60)是切片的张数;T是一个整数阈值(若疑似肿瘤的连通体体积小于T,则该小块忽略不计)。

最后给出L张切片。每张用一个由0和1组成的M×N的矩阵表示,其中1表示疑似肿瘤的像素,0表示正常像素。由于切片厚度可以认为是一个常数,于是我们只要数连通体中1的个数就可以得到体积了。麻烦的是,可能存在多个肿瘤,这时我们只统计那些体积不小于T的。两个像素被认为是“连通的”,如果它们有一个共同的切面,如下图所示,所有6个红色的像素都与蓝色的像素连通。

输出格式:

在一行中输出肿瘤的总体积。

输入样例:

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

题目看懂了其实就是搜索的一种变形,以前接触的多的是平面内的搜索,但是这道题加入了“立体”的概念,也就是在多个叠加的平面内搜索。在平面搜搜索的时候我们会给每个坐标点加上上下左右四个方向。那现在是立体搜索,那么就有 6 个方向,即多了上一层的相同横纵坐标点和下一层的相同横纵坐标点。说白了就是平面内的搜索有 x 和 y 两个坐标轴,现在变成了立体的搜索,那就要加上一个坐标轴即 z 轴。原来只有 x, y 坐标轴的时候有 4 个 方向,现在加上 z 轴就有 6 个方向。值的注意的是如果使用 dfs(深度优先搜索)是会段错误的,应该是递归层次太深,程序栈内存不足了。

第一份代码是直接用 dfs 做的,但是最后两个测试点段错误

// <!! 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 + 层数循环,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(宽度优先搜索)。为什么之前没想起来。。。我应该是活在梦里。。。

// 最后 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;
}

这份代码就 AC 了,只能说 BFS 大法好。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    指点
  • 查找算法

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

    指点
  • 八大经典排序算法总结

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

    指点
  • LeetCode Contest 166

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

    ShenduCC
  • 3117 高精度乘法

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

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

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

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题4-6 水仙花数

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

    C you again 的博客
  • 10:Challenge 3(树状数组直接修改)

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

    attack
  • Day2上午解题报告

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

    attack
  • P3808 【模版】AC自动机(简单版)

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

    attack

扫码关注云+社区

领取腾讯云代金券