1091. Acute Stroke.md

pat 甲级 1091. Acute Stroke

题意概述

题目给了一个$M×N×L$的三维图，找出这个三维图结点数量大于等于T的连通块，将每个这样的连通块的结点数量进行加和，然后输出。

输入输出格式

输入第一行给出 4 个正整数 M、N、L、T。接下来的输入分成 L 块，每块是$M×N$的矩阵。矩阵元素只有 1 和 0 两个值，值为 1 表示这是一个结点；值为 0 表示这是一个空结点。

输出大于等于T的连通块的结点总数。

数据规模

$$M<=1286,N<=128,L<=60$$

算法设计

使用 BFS 算法遍历每个连通块，求出其结点总数，将节点数量大于等于t的连通块的结点数量进行累计即可。

注意点

本题不能使用 DFS 遍历，否则会造成递归爆栈。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
using agg3 = array<gg, 3>;
bool graph[1300][130][70];
gg mi, ni, li, ti;
vector<agg3> dire{
    {-1, 0, 0}, {0, 1, 0}, {1, 0, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1},
};  // 6个方向
gg BFS(agg3 p) {
    gg ans = 0;  //当前连通块结点数量
    queue<agg3> q;
    q.push(p);
    graph[p[0]][p[1]][p[2]] = false;
    while (not q.empty()) {
        p = q.front();
        q.pop();
        ++ans;
        for (gg i = 0; i < 6; ++i) {
            gg x = p[0] + dire[i][0], y = p[1] + dire[i][1],
               z = p[2] + dire[i][2];
            if (x >= 0 and x < mi and y >= 0 and y < ni and z >= 0 and
                z < li and graph[x][y][z]) {
                q.push({x, y, z});
                graph[x][y][z] = false;
            }
        }
    }
    return ans >= ti ? ans : 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> mi >> ni >> li >> ti;
    for (gg k = 0; k < li; ++k) {
        for (gg i = 0; i < mi; ++i) {
            for (gg j = 0; j < ni; ++j) {
                cin >> graph[i][j][k];
            }
        }
    }
    gg ans = 0;
    for (gg k = 0; k < li; ++k) {
        for (gg i = 0; i < mi; ++i) {
            for (gg j = 0; j < ni; ++j) {
                if (graph[i][j][k]) {
                    ans += BFS({i, j, k});
                }
            }
        }
    }
    cout << ans;
    return 0;
}