Skip to content

L3-004 肿瘤诊断

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 600 ms
  • 内存限制: 64 MB

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

输入格式

输入第一行给出4个正整数：M、N、L、T，其中M和N是每张切片的尺寸（即每张切片是一个M\times N的像素矩阵。最大分辨率是1286\times 128）；L（\le 60）是切片的张数；T是一个整数阈值（若疑似肿瘤的连通体体积小于T，则该小块忽略不计）。

最后给出L张切片。每张用一个由0和1组成的M\times 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

Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pid pair<int, db>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 10010
int m, n, l, t;
int Move[][3] = {
        0,
        0,
        1,
        0,
        0,
        -1,
        0,
        1,
        0,
        0,
        -1,
        0,
        1,
        0,
        0,
        -1,
        0,
        0,
};
int G[61][1300][130];
int vis[61][1300][130];

bool ok(int x, int y, int z) {
    if (vis[x][y][z] || x <= 0 || x > l || y <= 0 || y > n || z <= 0 || z > m || !G[x][y][z])
        return 0;
    return 1;
}

struct node {
    int x, y, z;
    node() {}
    node(int x, int y, int z) : x(x), y(y), z(z) {}
};
int BFS(int x, int y, int z) {
    queue<node> q;
    q.push(node(x, y, z));
    vis[x][y][z] = 1;
    int res = 0;
    while (!q.empty()) {
        x = q.front().x, y = q.front().y, z = q.front().z;

        ++res;
        q.pop();
        for (int i = 0; i < 6; ++i) {
            int nx = x + Move[i][0];
            int ny = y + Move[i][1];
            int nz = z + Move[i][2];
            if (ok(nx, ny, nz)) {
                vis[nx][ny][nz] = 1;
                q.push(node(nx, ny, nz));
            }
        }
    }
    return res;
}

int main() {
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(vis, 0, sizeof vis);
    scanf("%d%d%d%d", &n, &m, &l, &t);
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= m; ++k) scanf("%d", &G[i][j][k]);
    int res = 0;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= m; ++k) {
                if (vis[i][j][k] || !G[i][j][k])
                    continue;
                int tmp = BFS(i, j, k);
                if (tmp >= t)
                    res += tmp;
            }
    cout << res << "\n";
    return 0;
}
Last update: May 4, 2022
Back to top