PAT甲级1091Acute Stroke

Posted on | | Visitors:
Words count in article: 776 字 | Reading time ≈ 4 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072

题目要求

  • 输入
    • M：正整数
    • N：正整数
    • L：正整数，不超过60，一个大脑中slice的数量
    • T：正整数，阈值，如果一个connected core的体积小于T，则这个core不能被计数
    • L个slice：每个slice是一个M×N的二值矩阵（1代表stroke，0代表正常），
  • 输出
    • 输出所有core的体积之和

题解一

解题思路

三维的图，一个结点和周围六个结点是相邻的，本质上还是求连通分量。

DFS，会段错误（Segmentation Fault），因为递归层数太多，堆栈溢出了。

代码

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
// Problem: PAT Advanced 1091
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072
// Tags: BFS 图 连通分量 DFS

#include <iostream>
using namespace std;

int m, n, l, t, volume;
int brain[65][1300][130];
bool visit[65][1300][130];
int bias[6][3] = {
    {-1, 0, 0},
    {1, 0, 0},
    {0, -1, 0},
    {0, 1, 0},
    {0, 0, -1},
    {0, 0, 1},
};

void dfs(int i, int j, int k){
    visit[i][j][k] = true;
    volume++;
    for (int biasIndex = 0, ii, jj, kk; biasIndex < 6; biasIndex++){
        ii = i + bias[biasIndex][0];
        jj = j + bias[biasIndex][1];
        kk = k + bias[biasIndex][2];
        if (!visit[ii][jj][kk] && brain[ii][jj][kk] == 1){
            dfs(ii, jj, kk);
        }
    }
}

int main()
{
    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", &brain[i][j][k]);
            }
        }
    }

    int volumeSum = 0;
    for (int i = 1; i <= l; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= n; k++){
                if (!visit[i][j][k] && brain[i][j][k] == 1){
                    volume = 0;
                    dfs(i, j, k);
                    if (volume >= t){
                        volumeSum += volume;
                    }
                }
            }
        }
    }
    printf("%d", volumeSum);
    return 0;
}

题解二

解题思路

用BFS方法遍历求连通分量

代码

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
// Problem: PAT Advanced 1091
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072
// Tags: BFS 图 连通分量 DFS

#include <iostream>
#include <queue>
using namespace std;

struct Node{
    int i, j, k;
};

int m, n, l, t, volume;
int brain[65][1300][130];
bool visit[65][1300][130];
Node bias[6] = {
    {-1, 0, 0},
    {1, 0, 0},
    {0, -1, 0},
    {0, 1, 0},
    {0, 0, -1},
    {0, 0, 1},
};

void bfs(Node node){
    queue<Node> nodes;
    nodes.push(node);
    visit[node.i][node.j][node.k] = true;
    while (!nodes.empty()){
        node = nodes.front();
        nodes.pop();
        volume++;
        for (int biasIndex = 0, ii, jj, kk; biasIndex < 6; biasIndex++){
            ii = node.i + bias[biasIndex].i;
            jj = node.j + bias[biasIndex].j;
            kk = node.k + bias[biasIndex].k;
            if (!visit[ii][jj][kk] && brain[ii][jj][kk]){
                nodes.push({ii, jj, kk});
                visit[ii][jj][kk] = true;
            }
        }
    }
}

int main()
{
    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", &brain[i][j][k]);
            }
        }
    }

    int result = 0;
    for (int i = 1; i <= l; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= n; k++){
                if (!visit[i][j][k] && brain[i][j][k]){
                    volume = 0;
                    bfs({i, j, k});
                    if (volume >= t){
                        result += volume;
                    }
                }
            }
        }
    }

    printf("%d", result);

    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!