【1091】Acute Stroke (30 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //利用BFS遍历,找到卒中核心块
     
    
   

    

     

    
    

     

      struct node{
     
    
   

    

     

    
    

     
	int x,y,z; //位置(x,y,z)
     
    
   

    

     

    
    

     

      }Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int n,m,slice,T;  //矩阵为n*m，共有slice层,T为卒中核心区中1的个数的下限
     
    
   

    

     

    
    

     

      int pixel[1290][130][61];  //三维01矩阵
     
    
   

    

     

    
    

     

      bool inq[1290][130][61] = {false}; //记录位置(x,y,z)是否已入过队
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int X[6]={0,0,0,0,1,-1}; //增量矩阵!!!一开始在1和-1之间漏了逗号。。。
     
    
   

    

     

    
    

     

      int Y[6]={0,0,1,-1,0,0};
     
    
   

    

     

    
    

     

      int Z[6]={1,-1,0,0,0,0};
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      int X[6] = {0, 0, 0, 0, 1, -1};
     
    
   

    

     

    
    

     

      int Y[6] = {0, 0, 1, -1, 0, 0};
     
    
   

    

     

    
    

     

      int Z[6] = {1, -1, 0, 0, 0, 0};
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool judge(int x,int y,int z){ //判断坐标(x,y,z)是否需要访问
     
    
   

    

     

    
    

     
	//越界返回false
     
    
   

    

     

    
    

     
	if(x>=n || x<0 || y>=m || y<0 || z>=slice || z<0)  return false;
     
    
   

    

     

    
    

     
	//若当前位置为0或(x,y,z)已入队，则返回false
     
    
   

    

     

    
    

     
	if(pixel[x][y][z] == 0 || inq[x][y][z] == true)  return false;
     
    
   

    

     

    
    

     
	//以上都不满足,返回true
     
    
   

    

     

    
    

     
	return true;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //BFS函数访问位置(x,y,z)所在的块,将该块所有"1"的inq都设置为true
     
    
   

    

     

    
    

     

      int BFS(int x,int y,int z){  
     
    
   

    

     

    
    

     
	int tot=0;   //计数当前块中1的个数
     
    
   

    

     

    
    

     

      	queue<node> Q; //定义队列
     
    
   

    

     

    
    

     

      	Node.x=x,Node.y=y,Node.z=z;  //结点Node的位置为(x,y,z)
     
    
   

    

     

    
    

     

      	Q.push(Node);  //将结点Node入队
     
    
   

    

     

    
    

     

      	inq[x][y][z]=true; //设置位置(x,y,z)已入过队
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	while( !Q.empty() ){
     
    
   

    

     

    
    

     

      		node top=Q.front();  //取出队首元素
     
    
   

    

     

    
    

     

      		Q.pop(); //队首元素出队
     
    
   

    

     

    
    

     

      		tot++; //当前块中1的个数加1
     
    
   

    

     

    
    

     
		for(int i=0;i<6;i++) {  //循环6次，得到6个增量方向
     
    
   

    

     

    
    

     
			int newX=top.x+X[i];
     
    
   

    

     

    
    

     
			int newY=top.y+	Y[i];
     
    
   

    

     

    
    

     
			int newZ=top.z+Z[i];
     
    
   

    

     

    
    

     
			if( judge(newX,newY,newZ) ) {   //新位置(newX,newY,newZ)需要访问
     
    
   

    

     

    
    

     
				//设置Node的坐标
     
    
   

    

     

    
    

     

      				Node.x=newX, Node.y=newY, Node.z=newZ;
     
    
   

    

     

    
    

     

      				Q.push(Node);  //将结点Node入队
     
    
   

    

     

    
    

     

      				inq[newX][newY][newZ]=true ;  //设置(newX,newY,newZ)已入过队
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	if(tot >= T) return tot;  //如果超过阈值,则返回
     
    
   

    

     

    
    

     
	else return 0; //否则不记录该块1的个数
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	scanf("%d%d%d%d",&n,&m,&slice,&T);	
     
    
   

    

     

    
    

     
	for(int z=0; z<slice; z++){  //注意先枚举切片层号!!!
     
    
   

    

     

    
    

     
		for(int x=0; x<n; x++){ 
     
    
   

    

     

    
    

     
			for(int y=0; y<m; y++){
     
    
   

    

     

    
    

     
				scanf("%d",&pixel[x][y][z]);
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int ans=0;  //记录卒中核心区中1的个数总和
     
    
   

    

     

    
    

     
	for(int z=0;z<slice; z++){
     
    
   

    

     

    
    

     
		for(int x=0;x<n ; x++) {
     
    
   

    

     

    
    

     
			for(int y=0;y<m; y++){
     
    
   

    

     

    
    

     
				//如果当前位置为1，且未被访问,则BFS当前块
     
    
   

    

     

    
    

     
				if(pixel[x][y][z]==1 && inq[x][y][z]==false){
     
    
   

    

     

    
    

     

      					ans += BFS(x,y,z);
     
    
   

    

     

    
    

     

      				}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("%d\n",ans);
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99248669