PAT甲级 1091 Acute Stroke 三维连通块问题
思路:
很典型的一道连通块问题,难点在于是三维的,因此增量数组需要有三个方向,并且还需统计每个块中包含的结点数量,如果数量小于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;
queueq;
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;
}
还没有评论,来说两句吧...