【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;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
81 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
124 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
112 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
109 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
89 0
|
C++
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
93 0
|
人工智能 BI C++
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
171 0
|
24天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
3天前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
31 16
|
7天前
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
46 6