搜索法 | 1091bfs搜索：三维bfs - 开发语言

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

首先我们来理解样例输入：

尺寸：3行4列5片阈值：2

样例中，一共有三块连通区域，分别是红色，蓝色，紫色。因为紫色的元素数小于2，所以不考虑。ans=26

编码过程中出现了很多bug，主要问题出在bfs结构的编写上。编写bfs结构一定要牢记“ 出队标记 ， 入队标记 ， 入队判断 ”这三个编写要点，就能保证AC。

代码：

#include <stdio.h>

#include <memory.h>

#include <math.h>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#define I scanf

#define OL puts

#define O printf

#define F(a,b,c) for(a=b;a<c;a++)

#define FF(a,b) for(a=0;a<b;a++)

#define FG(a,b) for(a=b-1;a>=0;a--)

#define LEN 1010

#define MAX 0x06FFFFFF

#define V vector<int>

using namespace std;

int g[][][];

int vis[][][];

int n,m,T,l,cnt;

typedef struct pt{

    int x,y,z;

    pt(int z=,int x=,int y=):x(x),y(y),z(z){    //注意第一个是组号

    }

};

void pushIn(int z,int x,int y,queue<pt> &q) {

    if(z<l && z>= && x<m && x>= && y<n && y>= && g[z][x][y] && !vis[z][x][y]){

        q.push(pt(z,x,y));

        vis[z][x][y]=;

        cnt++;

    }

}

int main(){

//    freopen("I:\\pat\\图的遍历\\1091.txt","r",stdin);

    int a,b,i,j,k;//行 列 组 阈值

    I("%d%d%d%d",&m,&n,&l,&T);

    FF(i,l)FF(j,m)FF(k,n){

        I("%d",&g[i][j][k]);//组 行 列

    }

    int ans=;

    FF(i,l)FF(j,m)FF(k,n) if(g[i][j][k] && !vis[i][j][k]){

        queue<pt>     q;

        q.push(pt(i,j,k));

        cnt=;

        while(!q.empty()){

            pt t=q.front();

            q.pop();

            int tx=t.x,ty=t.y,tz=t.z;

            vis[tz][tx][ty]=;

            //6个方向

            pushIn(tz+,tx,ty,q);

            pushIn(tz-,tx,ty,q);

            pushIn(tz,tx+,ty,q);

            pushIn(tz,tx-,ty,q);

            pushIn(tz,tx,ty+,q);

            pushIn(tz,tx,ty-,q);

        }

        if(cnt>=T){

            ans+=cnt;

        }

    }

    O("%d",ans);

    return ;

}