pat 甲级 团体天梯 L3-004. 肿瘤诊断

时间:2021-06-12 23:42:12

L3-004. 肿瘤诊断

时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越

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

输入格式:

输入第一行给出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个红色的像素都与蓝色的像素连通。

pat 甲级 团体天梯 L3-004. 肿瘤诊断
Figure 1

输出格式:

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

输入样例:
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

思路:上下前后左右六个方向搜索即可,用BFS好一些,dfs会爆
AC代码:
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<queue>
using namespace std;
#define N_MAX 1000+2
#define INF 0x3f3f3f3f
int N,M,L,T;//T为最小面积限制
int Map[61][1287][129];
bool vis[61][1287][129];
int pos_z[6] ={0,0,0,0,1,-1};
int pos_x[6] ={0,0,1,-1,0,0};
int pos_y[6] ={1,-1,0,0,0,0};
int area;
struct point {
  int x, y, z;
    point() {}
  point(int x,int y,int z):x(x),y(y),z(z) {}
};

void dfs(int x, int y, int z) {
  vis[z][x][y] = 1;
  area++;
  for (int i = 0; i < 6; i++) {
    int Z = z+pos_z[i],X=x+pos_x[i],Y=y+pos_y[i];
        if (X >= 0 && X <N && Y >= 0 && Y < M && Z >= 0 && Z < L && !vis[Z][X][Y]&&Map[Z][X][Y]==1) {
          dfs(X, Y, Z);
        }
      }
}

void bfs(int x,int y,int z) {
  queue<point>que;
  que.push(point(x,y,z));
  vis[z][x][y] = true;
  while (!que.empty()) {
    point P = que.front();que.pop();
    area++;
    for (int i = 0; i < 6;i++) {
      int Z =P.z + pos_z[i], X = P.x + pos_x[i], Y = P.y + pos_y[i];
      if (X >= 0 && X <N && Y >= 0 && Y < M && Z >= 0 && Z < L && !vis[Z][X][Y] && Map[Z][X][Y] == 1) {
        vis[Z][X][Y] = true;
        que.push(point(X, Y, Z));
      }
    }
  }
}

int main() {
  while (scanf("%d%d%d%d", &N,&M,&L,&T) != EOF) {
    memset(vis,0,sizeof(vis));
    for (int i = 0; i < L;i++) {
      for (int j = 0; j < N;j++) {
        for (int k = 0; k < M;k++) {
          scanf("%d", &Map[i][j][k]);
        }
      }
    }
    int cnt = 0;
    for (int i = 0; i < L; i++) {
      for (int j = 0; j < N; j++) {
        for (int k = 0; k < M; k++) {
          area = 0;
          if (!vis[i][j][k]&&Map[i][j][k]==1) {
            bfs(j, k, i);
            if (area >= T) {
              cnt += area;
            }
          }
        }
      }
    }
    printf("%d\n",cnt);
  }
  return 0;
}