Description
工業和醫學上經常要用到一種診斷技術——核磁共振成像(Magnetic Resonance Imagers)。利用該技術可以對三維物體(例如大腦)進行掃描。掃描的結果用一個三維的數組來儲存,數組的每一個元素表示空間的一個象素。數組的元素是0-255的整數,表示該象素的灰階。例如0表示該象素是黑色的,255表示該象素是白色的。
被掃描的物體往往是由若幹個部件組合而成的。例如臨床醫學要對病變的器官進行檢查,而器官是由一些不同的組織構成的。在實際問題中,同一個部件内部的色彩變化相對連續,而不同的部件的交界處色彩往往有突變。下面是一個簡化的植物細胞的例子。
從細胞的平面圖來看,該細胞大緻是由四個“部件”構成的,細胞壁、細胞核、液泡和細胞質。為了友善起見,我們對部件的概念做如下的規定:
1.如果一個象素屬于某部件,則或者該象素至少與該部件的一個象素相鄰,或者該象素單獨組成一個部件。(說明:每一個象素與前後、左右、上下的6個象素相鄰)
2.同一個部件内部,相鄰兩個象素的灰階差不超過正整數M。M決定了程式識别部件的靈敏度。
你的任務是對于給定的物體,判斷該物體是由幾個部件組成的。
Input
輸入資料由多組資料組成。每組資料格式如下:
第一行是三個正整數L,W,H(L,W,H≤50),表示物體的長、寬、高。
第二行是一個整數M(0≤M≤255),表示識别部件的靈敏度。
接下來是L×W×H個0-255的非負整數,按照空間坐标從小到大的順序依次給出每個象素的灰階。
說明:對于空間兩點P1(x1,y1,z1)和P2(x2,y2,z2),P1<P2當且僅當
(x1<x2)或者(x1=x2且y1<y2)或者(x1=x2且y1=y2且z1<z2)
Output
對于每組資料,輸出僅一行包含一個整數M,即一共識别出幾個部件。
Sample Input
2 2 2
1 1 1 1 2 2 2 2
Sample Output
2
其實就是找找有幾個連通塊,直接dfs記錄即可
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60;
int T,a,b,c,m,f[maxn][maxn][maxn],vis[maxn][maxn][maxn];
int q[6]={1,-1,0,0,0,0};
int w[6]={0,0,1,-1,0,0};
int e[6]={0,0,0,0,1,-1};
void dfs(int x,int y,int z)
{
if (vis[x][y][z]) return;
vis[x][y][z]=1;
for (int i=0;i<6;i++)
{
if (f[x+q[i]][y+w[i]][z+e[i]]!=-1)
{
if (abs(f[x+q[i]][y+w[i]][z+e[i]]-f[x][y][z])<=m)
{
dfs(x+q[i],y+w[i],z+e[i]);
}
}
}
}
int main()
{
while (~scanf("%d%d%d%d",&a,&b,&c,&m))
{
memset(f,-1,sizeof(f));
memset(vis,0,sizeof(vis));
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++)
for (int k=1;k<=c;k++) scanf("%d",&f[i][j][k]);
int cnt=0;
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++)
for (int k=1;k<=c;k++)
if (!vis[i][j][k]) {dfs(i,j,k); cnt++;}
printf("%d\n",cnt);
}
return 0;
}