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

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

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

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

**注意点：**

*  每个人的坐标系是不同的，因此在解题的时候先标注清楚每个方向所代表的意思，例如我的x轴为m,y轴为n，z轴为l，并且原点是第一点，一开始读入的面在最底层
 *  数组开的稍微大一点，例如最后一个测试点是极端数据，我一开始matrix数组不够大，存不下所有数据，找了好久才看到这个错误

#include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    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<node> q;
      q.push(Node);
      inq[z][x][y]=true;
      while(!q.empty())
      { 
        node it=q.front();
        q.pop();
        for(int i=0;i<6;i++)//查找六个方向
        { 
          int newx=it.x+dx[i];
          int newy=it.y+dy[i];
          int newz=it.z+dz[i];
          if(judge(newx,newy,newz))
          { 
            Node.x=newx;Node.y=newy;Node.z=newz;
            q.push(Node);
            ans++;
            inq[newz][newx][newy]=true;
          }
        }
      }
      return ans;
    }
    int main()
    { 
      cin>>m>>n>>l>>t;
      int sum=0;
      for(int i=0;i<l;i++)
      { 
        for(int j=0;j<m;j++)
        { 
          for(int k=0;k<n;k++)
          { 
            scanf("%d",&matrix[i][j][k]);
          }
        }
      }
      //遍历每个位置,如果当前位置属于病区并且未曾入队，bfs搜索附近所有1的区域并在inq标记为true表示已经入队过
      for(int i=0;i<l;i++)
      { 
        for(int j=0;j<m;j++)
        { 
          for(int k=0;k<n;k++)
          { 
            if(inq[i][j][k]==false&&matrix[i][j][k]==1)
            { 
              int temp=bfs(j,k,i);//todo
              if(temp>=t)sum+=temp;
            }
          }
        }
      }
      cout<<sum<<endl;
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230521/c1064ccc1f5a428f8541eb1140f2b1e3.png