Fork me on GitHub

PAT(甲级)渡劫(四)-Acute Stroke(30)


PAT(甲级)渡劫(四)-Acute Stroke(30)

题目大意:

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

算法思想:

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

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

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

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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int m,n,l,t;
bool slice[62][1288][130]; // 即输入
bool vis[62][1288][130]; // 标记对应的点是否访问过
int cnt = 0;
struct Node{
int i,j,k;
};

int BFS(int a,int b,int c){
if(vis[a][b][c] || slice[a][b][c] == false) // 若该处已经访问过,或者没有肿瘤则返回0
return 0;
// 该结点有肿瘤
Node t;
int i,j,k;
int res = 0;
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 == 0 || i > l || j == 0 || j > m || k == 0 || k>n) // 若该结点不在范围内,则跳过
continue;
res++; // 若该结点在范围内
// 六个方向
if(slice[i][j-1][k] && !vis[i][j-1][k]){ // 左
t.i = i;
t.j = j-1;
t.k = k;
q.push(t); // 若左边的结点没有被访问过,则入队列,并设置已经访问
vis[i][j-1][k] = true;
}
if(slice[i][j+1][k] && !vis[i][j+1][k]){ // 右
t.i = i;
t.j = j+1;
t.k = k;
q.push(t); // 若右边的结点没有被访问过,则入队列,并设置已经访问
vis[i][j+1][k] = true;
}
if(slice[i][j][k-1] && !vis[i][j][k-1]){ // 下
t.i = i;
t.j = j;
t.k = k-1;
q.push(t); // 若下边的结点没有被访问过,则入队列,并设置已经访问
vis[i][j][k-1] = true;
}
if(slice[i][j][k+1] && !vis[i][j][k+1]){ // 上
t.i = i;
t.j = j;
t.k = k+1;
q.push(t); // 若上边的结点没有被访问过,则入队列,并设置已经访问
vis[i][j][k+1] = true;
}
if(slice[i+1][j][k] && !vis[i+1][j][k]){ // 前
t.i = i+1;
t.j = j;
t.k = k;
q.push(t); // 若前边的结点没有被访问过,则入队列,并设置已经访问
vis[i+1][j][k] = true;
}
if(slice[i-1][j][k] && !vis[i-1][j][k]){ // 后
t.i = i-1;
t.j = j;
t.k = k;
q.push(t); // 若后边的结点没有被访问过,则入队列,并设置已经访问
vis[i-1][j][k] = true;
}
}
return res;
}

int main(){
//freopen("in.txt","r",stdin);
memset(vis,false,sizeof(vis));
memset(slice,false,sizeof(slice));
int a;
scanf("%d %d %d %d",&m,&n,&l,&t);
for(int i = 1 ; i <= l ; i++){
for(int j = 1 ; j <= m ; j++){
for(int k = 1 ; k <= n ; k++){
scanf("%d",&a);
if(a == 1)
slice[i][j][k] = true;
else
slice[i][j][k] = false;
}
}
}

int sum = 0;
for(int i = 1 ; i <= l ; i++){
for(int j = 1 ; j <= m ; j++){
for(int k = 1 ; k <= n ; k++){
cnt = BFS(i,j,k);
if(cnt >= t)
sum+=cnt;
}
}
}
printf("%d\n",sum);
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%