【PAT甲级 - C++题解】1091 Acute Stroke

简介: 【PAT甲级 - C++题解】1091 Acute Stroke

1091 Acute Stroke


One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.


Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M×N matrix, and the maximum resolution is 1286 by 128); L (≤60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).


Then L slices are given. Each slice is represented by an M×N matrix of 0’s and 1’s, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1’s to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.


6d3dfd98579f478aa23358f978fff3f0.jpg

Figure 1


Output Specification:

For each case, output in a line the total volume of the stroke core.


Sample Input:

3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0

Sample Output:

26


题意

这题实际上就是一个求连通块数量的题目,给定一个 L×M×N 的三维矩阵和一个常量 T ,每个坐标只与其上下左右前后相连通,一个连通块的面积大于等于 T 就算危险中风区域,现在要求我们计算该三维矩阵中危险中风区域的总面积。


思路

由于 PAT 的内存限制,如果用 dfs 会爆栈,所以这题我们用 bfs 来做,具体思路如下:


1.输入地图,用一个三维数组 g 来存储,1 表示中风区域,0 表示正常区域。

2.遍历数组中的每一个坐标,如果该位置是中风区域,则计算与其相连通的区域面积。

①bfs 需要用到队列,初始化队列,同时在数组 g 中标记当前坐标为 0 即表示已遍历过。

②每次遍历都从队列头部取出一个元素,然后判断其相邻的六个方向是否可达即同样也是中风区域,如果是则将该坐标加入到队列的尾部。

③每加入一个坐标到队列,当前连通块面积 cnt 就加 1 。

3.如果当前遍历的连通块面积大于等于 T ,就加入到总面积 res 当中。

4.输出危险中风总面积 res 。


代码

#include<bits/stdc++.h>
using namespace std;
const int M = 1300, N = 130, L = 65;
int g[L][M][N];
int m, n, l, T;
struct Node {
    int x, y, z;
};
int d[][3] = {
    {1,0,0},
    {-1,0,0},
    {0,1,0},
    {0,-1,0},
    {0,0,1},
    {0,0,-1}
};
//宽度优先搜索求连通块面积
int bfs(int x, int y, int z)
{
    //初始化
    queue<Node> q;
    q.push({ x,y,z });
    g[x][y][z] = 0;
    //开始宽搜
    int cnt = 1;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        //遍历6个方向
        for (int i = 0; i < 6; i++)
        {
            int a = t.x + d[i][0], b = t.y + d[i][1], c = t.z + d[i][2];
            if (a >= 0 && a < l && b >= 0 && b < m && c >= 0 && c < n && g[a][b][c])
            {
                g[a][b][c] = 0;
                q.push({ a,b,c });
                cnt++;
            }
        }
    }
    return cnt;
}
int main()
{
    //输入地图
    scanf("%d%d%d%d", &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", &g[i][j][k]);
    //计算危险中风区域面积
    int res = 0;
    for (int i = 0; i < l; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < n; k++)
                if (g[i][j][k])
                {
                    int cnt = bfs(i, j, k);
                    if (cnt >= T)  res += cnt;
                }
    //输出总面积
    printf("%d\n", res);
    return 0;
}
目录
打赏
0
0
0
0
37
分享
相关文章
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
86 0
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
131 0
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
118 0
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
114 0
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
91 0
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
95 0
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
174 0
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
38 16
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等