PAT A1091 Acute Stroke

题目说明：

提供一个三维空间，一个值为1的结点和它上下左右前后值为1的结点构成一个块；要求统计结点数大于等于T的块，合计的结点数。

思路：

1.建立三维数组，保存数据；为方便访问当前结点相邻位置，建立一个结点结构保存（x,y,z）坐标；数组要建立在主函数外面，最后两个测试数据量过大，建立在主函数内会报错；

2.三层循环遍历每一个结点；

1）若结点值为1且未被访问，说明遇到了一个新的块，按广度优先搜索遍历与当前结点相邻且值为1的结点；若块中的1数量>=T，则答案增加相应数量，否则跳过；

AC代码：

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;

//保存 前后上下左右 6个方位的相对坐标 
int ix[6]={-1,1,0,0,0,0};//左右上下前后 
int iy[6]={0,0,0,0,1,-1};
int iz[6]={0,0,1,-1,0,0};

int M,N,L,T;
struct Node
{
	short data;
	int x,y,z;
	bool inq;//标记是否入队 
};
Node table[60][1286][128];

int main()
{
	freopen("text.txt","r",stdin);
	cin>>M>>N>>L>>T;
	for(int i=0;i<L;i++)
	{
		for(int j=0;j<M;j++)
		{
			for(int k=0;k<N;k++)
			{
				scanf("%d",&table[i][j][k].data);
				table[i][j][k].x=k;
				table[i][j][k].y=j;
				table[i][j][k].z=i;
				table[i][j][k].inq=false;
				
			}
		}
	}
	int ans=0,count;//ans保存答案，count为当前块1的个数 
	Node temp;
	queue<Node> Q;//队列，广度优先遍历 使用 
	int x,y,z;//存放坐标
	//三层循环，遍历数据 
	for(int i=0;i<L;i++)
	{
		for(int j=0;j<M;j++)
		{
			for(int k=0;k<N;k++)
			{
				//当 访问的结点为1 且 未进入过队列 说明访问到一个新块 
				//则 结点进入队列并按广度搜索 
				if(table[i][j][k].inq==false&&table[i][j][k].data==1)
				{
					count=1;//当前有一个 1 
					Q.push(table[i][j][k]);
					table[i][j][k].inq=true;// 标记入队 
					while(!Q.empty())//广度优先搜索 
					{
						temp=Q.front();Q.pop();
						for(int t=0;t<6;t++)
						{
							//更新相邻数据的坐标 
							z=temp.z+iz[t];
							y=temp.y+iy[t];
							x=temp.x+ix[t];
							//判断坐标是否合法 
							if(z<0||z>=L||y<0||y>=M||x<0||x>=N) continue;
							//若相邻位置未被访问 且 数据为1 则入队 
							if(table[z][y][x].inq==false&&table[z][y][x].data==1)
							{
								Q.push(table[z][y][x]);
								table[z][y][x].inq=true;
								count++;//当前 块 计数加1 
							}
						}//t
					}//while
					if(count>=T) ans+=count;//若块的计数大于T 则 修改ans 
				}//if	
			}//k
		}//j
	}//i
	cout<<ans;
}