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个红色的像素都与蓝色的像素连通。【这句话是重点，还有就是像素是什么鬼？！看了好长时间，最后大致看明白了！题意需要审清楚！还有就是切片的问题，题目中给的切片是摞起来一层一层的？还是在同一个平面上平着切下的呢？！——后来查了查资料原来是切片一层一层切下去的！/逃】

输出格式：

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

输入样例：

......

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<vector>

 #include<string>

 #include<stack>

 #define  inf 0x3f3f3f3f

 using namespace std;   //L3-004, 肿瘤诊断

 #define N 200

 #define ll long long

 int mp[][N][N];//这里不能开的太大，太小会WA，太大会炸！

 int vis[][N][N];

 int dir[][]={ {,,},{,,},{,,},{-,,},{,-,},{,,-}  };

 struct node{

     int x,y,z;

     node(int x=,int y=,int z=):x(x),y(y),z(z){}//类似Java的类的构造方法，可以让 st=node(i0,j0,k0) 直接实现！！

 };

 int m,n,l,T;//l表示层数，T表示阈值(表示组合成联通块的最小合格体积)

 int bfs(int i0,int j0,int k0){//以下为bfs常规基本套路，不多解释

     int ans=;

     node st,now,ne;

     st=node(i0,j0,k0);

     queue<node>Q;

     Q.push(st);

     vis[i0][j0][k0]=;

     while(Q.size()>){

         now=Q.front();

         Q.pop();

         for(int i=;i<;i++){

             ne.x=now.x+dir[i][];

             ne.y=now.y+dir[i][];

             ne.z=now.z+dir[i][];

             if(ne.x<||ne.x>l||ne.y<||ne.y>m||ne.z<||ne.z>n)

                 continue;

             else if(vis[ne.x][ne.y][ne.z]==||mp[ne.x][ne.y][ne.z]==)

                 continue;

             else{

                 vis[ne.x][ne.y][ne.z]=;

                 Q.push(ne);

                 ans++;

             }

       }

     }

     return (ans>=T?ans:);

 }

 int main(){

     int num;

     scanf("%d%d%d%d",&m,&n,&l,&T);

     for(int i=;i<=l;i++){

         for(int j=;j<=m;j++){

             for(int k=;k<=n;k++){

                 scanf("%d",&mp[i][j][k]);

             }

         }

     }

     memset(vis,,sizeof(vis));

     int ans=;

      for(int i=;i<=l;i++){

         for(int j=;j<=m;j++){

             for(int k=;k<=n;k++){

                 if(mp[i][j][k]==&&!vis[i][j][k])//符合两个条件，即可开始

                     ans+=bfs(i,j,k);

             }

         }

     }

     printf("%d\n",ans);

     return ;

 }

（带点注释~~）

DFS不知道行不行，具体自行试试！

巴特西

【经典/基础BFS+略微复杂的题意】PAT-L3-004. 肿瘤诊断

L3-004. 肿瘤诊断

最新文章

热门文章