PAT甲级 1091 Acute Stroke 三维连通块问题

淡淡的烟草味﹌ 2023-05-21 07:22 73阅读 0赞

\*\*加粗样式\*\*在这里插入图片描述
思路：
很典型的一道连通块问题，难点在于是三维的，因此增量数组需要有三个方向，并且还需统计每个块中包含的结点数量，如果数量小于t，不计数

实现步骤
1.枚举每一个位置，如果是0，跳过；如果是1，bfs搜索附近相连的所有为1的元素位置，并将inq数组置为true，以防止走回头路
2.judge函数判断当前搜索的位置是否合法
3.bfs需要有返回值，即当前块中1的数量，入队一个1，递增一下

注意点：

  • 每个人的坐标系是不同的，因此在解题的时候先标注清楚每个方向所代表的意思，例如我的x轴为m,y轴为n，z轴为l，并且原点是第一点，一开始读入的面在最底层

  • 数组开的稍微大一点，例如最后一个测试点是极端数据，我一开始matrix数组不够大，存不下所有数据，找了好久才看到这个错误

    include

    include

    include

    include

    using namespace std;
    struct node{
    int x,y,z;
    }Node;
    int m,n,l,t;
    bool inq[65][1290][130]={ false};
    int matrix[64][1290][130];
    int dx[6]={ 0,0,0,0,1,-1};
    int dy[6]={ 1,-1,0,0,0,0};
    int dz[6]={ 0,0,1,-1,0,0};
    bool judge(int x,int y,int z)
    {
    if(x<0||x>m-1||y<0||y>n-1||z<0||z>l-1)return false;
    else if(inq[z][x][y]==true||matrix[z][x][y]==0)return false;//已经入队或者当前位置是正常的
    else return true;
    }
    int bfs(int x,int y,int z)//返回每次遍历得到的病理位置总数
    {
    Node.x=x;Node.y=y;Node.z=z;
    int ans=1;
    queue q;
    q.push(Node);
    inq[z][x][y]=true;
    while(!q.empty())
    { 

    1. node it=q.front();
    2. q.pop();
    3. for(int i=0;i<6;i++)//查找六个方向
    4. { 
    5.   int newx=it.x+dx[i];
    6.   int newy=it.y+dy[i];
    7.   int newz=it.z+dz[i];
    8.   if(judge(newx,newy,newz))
    9.   { 
    10.     Node.x=newx;Node.y=newy;Node.z=newz;
    11.     q.push(Node);
    12.     ans++;
    13.     inq[newz][newx][newy]=true;
    14.   }
    15. }

    }
    return ans;
    }
    int main()
    {
    cin>>m>>n>>l>>t;
    int sum=0;
    for(int i=0;i<l;i++)
    { 

    1. for(int j=0;j<m;j++)
    2. { 
    3.   for(int k=0;k<n;k++)
    4.   { 
    5.     scanf("%d",&matrix[i][j][k]);
    6.   }
    7. }

    }
    //遍历每个位置,如果当前位置属于病区并且未曾入队，bfs搜索附近所有1的区域并在inq标记为true表示已经入队过
    for(int i=0;i<l;i++)
    { 

    1. for(int j=0;j<m;j++)
    2. { 
    3.   for(int k=0;k<n;k++)
    4.   { 
    5.     if(inq[i][j][k]==false&&matrix[i][j][k]==1)
    6.     { 
    7.       int temp=bfs(j,k,i);//todo
    8.       if(temp>=t)sum+=temp;
    9.     }
    10.   }
    11. }

    }
    cout<<sum<<endl;
    return 0;
    }

发表评论

表情：
评论列表 （有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读