L3-004 肿瘤诊断 [BFS]

时间:2023-02-07 23:41:09

三维BFS求连通块,当模版文章发了。

注意一下三维数组的参量对应的范围。

L3-004 肿瘤诊断 [BFS]L3-004 肿瘤诊断 [BFS]
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#include <queue>
#include <vector>
#define maxn
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct point
{
    int x,y,z;
};
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int m,n,l,t;
int ma[1290][130][65],vis[1290][130][65];
bool check(int x,int y,int z)
{
    if(x<0||x>=m||y<0||y>=n||z<0||z>=l||ma[x][y][z]==0)
        return  false;
    return true;

}
int BFS(int x,int y,int z)
{
    int res=1;
    point p,tp,tn;
    p.x=x;
    p.y=y;
    p.z=z;
    queue<point> q;
    q.push(p);
    vis[x][y][z]=1;
    while(!q.empty())
    {
        tp=q.front();
        q.pop();
        for(int i=0;i<6;i++)
        {
            int tx=tp.x+dx[i];
            int ty=tp.y+dy[i];
            int tz=tp.z+dz[i];
            if(check(tx,ty,tz)&&!vis[tx][ty][tz])
            {
                res++;
                vis[tx][ty][tz]=1;
                tn.x=tx;
                tn.y=ty;
                tn.z=tz;
                q.push(tn);
            }
        }
    }
    if(res>=t)
        return  res;
    return 0;
}
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d%d%d%d",&m,&n,&l,&t);
    for(int i=0;i<l;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<n;k++)
                scanf("%d",&ma[j][k][i]);
    int ans=0;
    for(int i=0;i<l;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<n;k++)
                if(ma[j][k][i]==1&&vis[j][k][i]==0)
                    ans+=BFS(j,k,i);
    printf("%d\n",ans);
    return 0;
}
View Code