Acwing.1581 急性中风
1581. 急性中风 - AcWing题库
题号:Acwing.1581 急性中风
题目类型:深搜 or 宽搜
简要做题思路:输入:三维数组的输入x、y、z要搞清代表什么 -> 循环遍历数组,深搜寻找每个符合条件的连通块 -> 判断连通块大小是否符合标准 -> 输出
#include <bits/stdc++.h>
using namespace std;
const int M = 1286, N = 128, L = 60;
int g[L][M][N];//用三维数组记录
int n, m, l, t;
int dx[] = {-1, 0, 1, 0, 0, 0};//三个偏移量数组
int dy[] = {0, 1, 0, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
int dfs(int z, int y, int x) {
int cnt = 1;//计数
g[z][y][x] = 0;//标记已经看过(可以少写1个st数组,节省空间)
for (int i = 0; i < 6; ++ i) {
int nz = z + dz[i], ny = y + dy[i], nx = x + dx[i];//开始使用偏移量一次枚举
if (nz < 0 || nz >= l || ny < 0 || ny >= m || nx < 0 || nx >= n || g[nz][ny][nx] == 0) continue;
cnt += dfs(nz, ny, nx);// 从当前位置开始继续深搜
}
return cnt;
}
int main() {
cin >> 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)
cin >> 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 = dfs(i, j, k);//深搜确定每一组有多少个中风区域
if (cnt >= t) res += cnt;//如果中风连通区域大于标准值,则记录
}
}
}
}
printf("%d", res);//输出
return 0;
}