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

淡淡的烟草味﹌ 2023-05-21 07:22 70阅读 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 条评论,70人围观)

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

相关阅读