題目地址:https://www.patest.cn/contests/gplt/L3-004
腫瘤診斷
在診斷腫瘤疾病時,計算腫瘤體積是很重要的一環。給定病灶掃描切片中標注出的疑似腫瘤區域,請你計算腫瘤的體積。
輸入第一行給出4個正整數:MM、NN、LL、TT,其中MM和NN是每張切片的尺寸(即每張切片是一個M/times NM×N的像素矩陣。最大分辨率是1286/times 1281286×128);LL(/le 60≤60)是切片的張數;TT是一個整數閾值(若疑似腫瘤的連通體體積小于TT,則該小塊忽略不計)。
最后給出LL張切片。每張用一個由0和1組成的M/times NM×N的矩陣表示,其中1表示疑似腫瘤的像素,0表示正常像素。由于切片厚度可以認為是一個常數,于是我們只要數連通體中1的個數就可以得到體積了。麻煩的是,可能存在多個腫瘤,這時我們只統計那些體積不小于TT的。兩個像素被認為是“連通的”,如果它們有一個共同的切面,如下圖所示,所有6個紅色的像素都與藍色的像素連通。
在一行中輸出腫瘤的總體積。
3 4 5 21 1 1 11 1 1 11 1 1 10 0 1 10 0 1 10 0 1 11 0 1 10 1 0 00 0 0 01 0 1 10 0 0 00 0 0 00 0 0 10 0 0 11 0 0 0輸出樣例:
26不知道這題用DFS為什么會有兩個案例段錯誤,難道是爆了系統棧?知道的大神能不能告訴一下,謝了。。。DFS代碼:#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <stack>#include <map>#include <algorithm>#include <vector>#include <string>#include <cstring>#include <sstream>using namespace std;int pic[80][1300][150];bool vis[80][1300][150];int m,n,h,T;int cnt;int di[10]={-1,1,0,0,0,0};int dj[10]={0,0,-1,1,0,0};int dk[10]={0,0,0,0,1,-1};void dfs(int i,int j,int k){ if(i<0||i>=h||j<0||j>=m||k<0||k>=n) return; if(vis[i][j][k]==true) return; if(pic[i][j][k]==0) return; vis[i][j][k]=true; cnt++; for(int a=0; a<6; a++) { int x=i+di[a]; int y=j+dj[a]; int z=k+dk[a]; dfs(x,y,z); }}int main(){ memset(vis,false,sizeof(vis)); scanf("%d%d%d%d",&m,&n,&h,&T); for(int i=0;i<h;i++) { for(int j=0;j<m;j++) { for(int k=0;k<n;k++) { scanf("%d",&pic[i][j][k]); } } } int ans=0; for(int i=0;i<h;i++) { for(int j=0;j<m;j++) { for(int k=0;k<n;k++) { if(vis[i][j][k]==false&&pic[i][j][k]==1) { cnt=0; dfs(i,j,k); if(cnt>=T) { ans+=cnt; } } } } } PRintf("%d/n",ans); return 0;}BFS代碼:#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <stack>#include <map>#include <algorithm>#include <vector>#include <string>#include <cstring>#include <sstream>using namespace std;int pic[80][1300][150];bool vis[80][1300][150];int m,n,h,T;int cnt;int di[10]={-1,1,0,0,0,0};int dj[10]={0,0,-1,1,0,0};int dk[10]={0,0,0,0,1,-1};int ans;struct note{ int i,j,k; note(int x,int y,int z) { i=x; j=y; k=z; }};typedef struct note note;queue<note> Q;void bfs(int i,int j,int k){ note tmp(i,j,k); Q.push(tmp); while(!Q.empty()) { note a=Q.front(); Q.pop(); if(a.i>=0&&a.i<h&&a.j>=0&&a.j<m&&a.k>=0&&a.k<n) { if(vis[a.i][a.j][a.k]==false && pic[a.i][a.j][a.k]==1) { vis[a.i][a.j][a.k]=true; cnt++; for(int c=0; c<6; c++) { int x=a.i+di[c]; int y=a.j+dj[c]; int z=a.k+dk[c]; if(x>=0&&y>=0&&z>=0&&x<h&&y<m&&z<n&&vis[x][y][z]==false&&pic[x][y][z]==1) { note temp(x,y,z); Q.push(temp); } } } } }}int main(){ memset(vis,false,sizeof(vis)); scanf("%d%d%d%d",&m,&n,&h,&T); for(int i=0;i<h;i++) { for(int j=0;j<m;j++) { for(int k=0;k<n;k++) { scanf("%d",&pic[i][j][k]); } } } for(int i=0;i<h;i++) { for(int j=0;j<m;j++) { for(int k=0;k<n;k++) { if(vis[i][j][k]==false&&pic[i][j][k]==1) { cnt=0; bfs(i,j,k); if(cnt>=T) { ans+=cnt; } } } } } printf("%d/n",ans); return 0;}
新聞熱點
疑難解答