PAT甲题题解-1091. Acute Stroke (30)-BFS

时间:2023-03-08 21:07:17

题意:给定三维数组,0表示正常,1表示有肿瘤块,肿瘤块的区域>=t才算是肿瘤,求所有肿瘤块的体积和

这道题一开始就想到了dfs或者bfs,但当时看数据量挺大的,以为会导致栈溢出,所以并没有立刻写,想有没有别的办法。
然而结果是,实在想不出别的办法了,所以还是尝试写写dfs、bfs。

一开始先用了dfs,最后两个样例段错误,估计是栈溢出了。
之所以dfs栈溢出,因为dfs的时候每个状态都会存储在堆栈里,就好比dfs的第一个状态,一直保存到最后整个dfs结束。
而bfs是存储在队列中,每次队列都会有状态取出来,所以栈存储就会少很多。

对于每次bfs,计算肿瘤块体积,如果>=t,才算入总和sum中。
用vis[i][j][k]标记结点是否被访问过,被访问过的就不会再次访问,即不会再加入到队列中去。

PS:这里slice和vis数组开成了62*1288*130,即每个维度都比原来多2,是为了处理数组越界

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int m,n,l,t;
bool slice[][][]; //即输入
bool vis[][][]; //标记对应的点是否访问过
int cnt=;
struct Node{
int i,j,k;
};
int BFS(int a,int b,int c){
if(vis[a][b][c] || slice[a][b][c]==false)
return ;
Node t;
int i,j,k;
int res=;
queue<Node>q;
t.i=a;
t.j=b;
t.k=c;
q.push(t);
vis[a][b][c]=true;
while(!q.empty()){
t=q.front();
q.pop();
i=t.i;
j=t.j;
k=t.k;
if(i== || i>l || j== || j>m || k== || k>n)
continue;
res++;
//六个方向
if(slice[i][j-][k] && !vis[i][j-][k]){
t.i=i;
t.j=j-;
t.k=k;
q.push(t);
vis[i][j-][k]=true;
}
if(slice[i][j+][k] && !vis[i][j+][k]){
t.i=i;
t.j=j+;
t.k=k;
q.push(t);
vis[i][j+][k]=true;
}
if(slice[i][j][k-] && !vis[i][j][k-]){
t.i=i;
t.j=j;
t.k=k-;
q.push(t);
vis[i][j][k-]=true;
}
if(slice[i][j][k+] && !vis[i][j][k+]){
t.i=i;
t.j=j;
t.k=k+;
q.push(t);
vis[i][j][k+]=true;
}
if(slice[i+][j][k] && !vis[i+][j][k]){
t.i=i+;
t.j=j;
t.k=k;
q.push(t);
vis[i+][j][k]=true;
}
if(slice[i-][j][k] && !vis[i-][j][k]){
t.i=i-;
t.j=j;
t.k=k;
q.push(t);
vis[i-][j][k]=true;
}
}
return res;
}
int main()
{
memset(vis,false,sizeof(vis));
memset(slice,false,sizeof(slice));
int a;
scanf("%d %d %d %d",&m,&n,&l,&t);
for(int i=;i<=l;i++){
for(int j=;j<=m;j++){
for(int k=;k<=n;k++){
scanf("%d",&a);
if(a==)
slice[i][j][k]=true;
else
slice[i][j][k]=false;
}
}
} int sum=;
for(int i=;i<=l;i++){
for(int j=;j<=m;j++){
for(int k=;k<=n;k++){
cnt=BFS(i,j,k);
if(cnt>=t)
sum+=cnt;
}
}
}
printf("%d\n",sum);
return ;
}