L3-004 肿瘤诊断 （30 分) bfs+连通块个数
发布时间
阅读量：
阅读量
在诊断肿瘤疾病时，计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域，请你计算肿瘤的体积。
输入格式：
输入第一行给出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
- 也是个纸老虎hhh
- 和上题一样bfs搜就完事了
- 6个方向搜索
- 搜完判断是否大于t即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//Constant area
const int MAXN=1000000;
const int MIN_INF=0x80000000;
const int MAX_INF=0x7fffffff;
//Variable area
int n,m,l,t,size,ans;
bool ma[61][1300][130];
bool vis[61][1300][130];
int di[6]={0,0,0,0,-1,1};
int dj[6]={0,0,-1,1,0,0};
int dk[6]={-1,1,0,0,0,0};
struct p{
int i,j,k;
};
queue<p> q;
//Initialization area
void init(){
memset(vis,0,sizeof(vis));
return;
}
//Function area
bool ok(p now){
if(now.i<1||now.i>l||now.j<1||now.j>n||now.k<1||now.k>m)
return false;
if(ma[now.i][now.j][now.k]==0)
return false;
if(vis[now.i][now.j][now.k]==true)
return false;
return true;
}
int search(int sti,int stj,int stk){
while(q.size())
q.pop();
q.push({sti,stj,stk});
size=1;
vis[sti][stj][stk]=true;
while(q.size()){
p now=q.front();
q.pop();
for(int i=0;i<6;i++){
p nex;
nex.i=now.i+di[i];
nex.j=now.j+dj[i];
nex.k=now.k+dk[i];
if(ok(nex)){
vis[nex.i][nex.j][nex.k]=true;
size++;
q.push(nex);
}
}
}
return size>=t? size:0;
}
int main(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cin>>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++){
cin>>ma[i][j][k];
}
}
}
ans=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]==0&&ma[i][j][k]==1){
ans+=search(i,j,k);
}
}
}
}
cout<<ans<<endl;
}
全部评论 (0)
还没有任何评论哟~