PAT甲级1091.

目录

A1091

题目

样例

输入:

3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0

输出:

26

思路和坑点

　　实际上是一个三维空间中“图”的bfs搜索，通过bfs搜索找到节点数大于指定阈值的连通分量的个数，借鉴《算法笔记》上的写法，使用增量矩阵来对一个坐标点周围的点进行遍历判别。主要在于理解题意，难点在于坐标点有效性的判定。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int x,y,z;
    node():x(0),y(0),z(0){}
    node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
}Node;
int n,m,slice,T;
int G[1290][130][61];                   //记录像素的坐标 
bool inq[1290][130][61]={false};        //记录是否已被访问
int X[6]={1,-1,0,0,0,0,};               //六个方向坐标的增量矩阵 
int Y[6]={0,0,1,-1,0,0,};
int Z[6]={0,0,0,0,1,-1,}; 
bool judge(int x,int y,int z);          //判断是否应该访问该点 
int BFS(int x,int y,int z);             //返回对该坐标BFS遍历得到的中风核心中1的个数 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d%d%d",&m,&n,&slice,&T);
    for(int i=0;i<slice;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<n;k++){
                scanf("%d",&G[j][k][i]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<slice;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<n;k++){
                if(G[j][k][i]==1&&inq[j][k][i]==false){
                    ans+=BFS(j,k,i);
                }
            }
        }
    }
    cout<<ans;
    return 0;    
}
bool judge(int x,int y,int z)           //坐标判定 
{
    if(x<0||x>=m||y<0||y>=n||z<0||z>=slice)        return false;//坐标越界不访问
    else if(G[x][y][z]==0||inq[x][y][z]==true)    return false; //像素是0，正常区域，或者已被访问，则不访问
    else return true;                                           //除了以上情况都进行访问 
 } 
int BFS(int x,int y,int z){             //bfs遍历函数 
    int total=0;                        //统计该块中1的个数
    queue<Node> q;                      //BFS的队列
    q.push(node(x,y,z));
    inq[x][y][z]=true;
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        total++;
        for(int i=0;i<6;i++){
            int nx=now.x+X[i];     int ny=now.y+Y[i];    int nz=now.z+Z[i];
            if(judge(nx,ny,nz)==true){
                q.push(node(nx,ny,nz));
                inq[nx][ny][nz]=true;
            }
            
        }
    } 
    if(total>=T) return total;        //如果超过阈值，返回1的个数，否则不计算在内，返回0 
    else          return 0;
}