三维扫描 FZU 1063

时间：2021-09-13 18:40:58

Description

工业和医学上经常要用到一种诊断技术——核磁共振成像（Magnetic Resonance Imagers）。利用该技术可以对三维物体(例如大脑)进行扫描。扫描的结果用一个三维的数组来保存，数组的每一个元素表示空间的一个象素。数组的元素是0－255的整数，表示该象素的灰度。例如0表示该象素是黑色的，255表示该象素是白色的。

被扫描的物体往往是由若干个部件组合而成的。例如临床医学要对病变的器官进行检查，而器官是由一些不同的组织构成的。在实际问题中，同一个部件内部的色彩变化相对连续，而不同的部件的交界处色彩往往有突变。下面是一个简化的植物细胞的例子。

三维扫描 FZU 1063从细胞的平面图来看，该细胞大致是由四个“部件”构成的，细胞壁、细胞核、液泡和细胞质。为了方便起见，我们对部件的概念做如下的规定： 
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 0 1 1 1 1 2 2 2 2

Sample Output

2
 
 
 
#include <iostream>

#include <cmath>

#include <cstdio>

using namespace std;

int a[][][][];

void dns(int i,int j,int k,int m)

{

    if(a[i][j][k][]>&&a[i][j][k+][]<&&a[i][j][k+][]>=&&abs(a[i][j][k][]-a[i][j][k+][])<=m)

    {

        a[i][j][k+][]=a[i][j][k][];

        dns(i,j,k+,m);

    }

    if(a[i][j][k][]>&&a[i][j][k-][]<&&a[i][j][k-][]>=&&abs(a[i][j][k][]-a[i][j][k-][])<=m)

    {

        a[i][j][k-][]=a[i][j][k][];

        dns(i,j,k-,m);

    }

    if(a[i][j][k][]>&&a[i][j-][k][]<&&a[i][j-][k][]>=&&abs(a[i][j][k][]-a[i][j-][k][])<=m)

    {

        a[i][j-][k][]=a[i][j][k][];

        dns(i,j-,k,m);

    }

    if(a[i][j][k][]>&&a[i][j+][k][]<&&a[i][j+][k][]>=&&abs(a[i][j][k][]-a[i][j+][k][])<=m)

    {

        a[i][j+][k][]=a[i][j][k][];

        dns(i,j+,k,m);

    }

    if(a[i][j][k][]>&&a[i-][j][k][]<&&a[i-][j][k][]>=&&abs(a[i][j][k][]-a[i-][j][k][])<=m)

    {

        a[i-][j][k][]=a[i][j][k][];

        dns(i-,j,k,m);

    }

    if(a[i][j][k][]>&&a[i+][j][k][]<&&a[i+][j][k][]>=&&abs(a[i][j][k][]-a[i+][j][k][])<=m)

    {

        a[i+][j][k][]=a[i][j][k][];

        dns(i+,j,k,m);

    }

}

int main()

{

    int l,w,h,m;

    while((scanf("%d%d%d%d",&l,&w,&h,&m))!=EOF)

    {

        memset(a,-,sizeof(a));

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

        {

            for(int j=;j<=w;j++)

            {

                for(int k=;k<=h;k++)

                {

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

                }

            }

        }

        int num=;

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

        {

            for(int j=;j<=w;j++)

            {

                for(int k=;k<=h;k++)

                {

                    if(a[i][j][k][]<&&a[i][j][k][]>=)

                    {

                        num++;

                        a[i][j][k][]=num;

                        dns(i,j,k,m);

                    }

                }

            }

        }

        cout<<num<<endl;

    }

}
这道题我用的DNS（深度优先搜索 ） 
 

相关文章