题目描述

！！连通：当前片，若其前后上下左右这6个位置的任意一个也是1，即连通
Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1

错误想法：以为上下左右都要连通才可以

判断连通：int 坐标数组，bfs遍历6个方向，也是1，cnt++；即可

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int M=1286,N =128,L=60;
int m,n,l,T;
int g[L][M][N];
struct Node
{
    int x,y,z;
};
//6个方向：x方向，y,z 
int d[][3]={//6*3的数组：6行3列（6个{}，每个中3个元素 
    {1,0,0},
    {-1,0,0},
    {0,1,0},
    {0,-1,0},
    {0,0,1},
    {0,0,-1},   
};

int bfs(int x,int y,int z)//return 连通的1的个数 
{
    queue<Node> q;
    q.push({x,y,z});//队列初始化，加入起点
    g[x][y][z]=0;//遍历过的点清0,只有1才进入bfs

    int cnt=1; //当前块内的点数 
    while(q.size())
    {
        //取出队头（赋值并删掉）
        auto t = q.front();
        q.pop();

        //遍历当前块能到的块 
        for(int i=0;i<6;i++)
        {
            int a=t.x+d[i][0],//x方向的取值6种，数组的第一维 
            b=t.y+d[i][1], c=t.z+d[i][2];
        //  cout<<a<<" "<<b<<" "<<c<<endl;
            //边界判断&&没被遍历过——加入队列 
            //cout<<"g[]="<<g[a][b][c]<<endl;
        //  cout<<n<<"!!!"<<endl;
            if(a>=0&&a<l&&b>=0&&b<m&&c>=0&&c<n&&g[a][b][c])

            {
                g[a][b][c]=0;//遍历过就要清空 
                q.push({a,b,c});

                cnt++;
            //  cout<<"cnt"<<cnt<<endl;
             } 
        }
    }
    return cnt;
}
int main()
{

    freopen("1.txt","r",stdin);
    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",&g[i][j][k]);

    int res=0;
    for(int i=0;i<l;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<n;k++)
                if(g[i][j][k])//1
                {
                    int t=bfs(i,j,k);//传入起点三个维度的下标 
                    //  cout<<t<<endl;
                    if(t>=T) 
                    res+=t;
                }

    printf("%d\n",res);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla