FloodFill算法 DFS
版
#include <iostream>
#include <vector>
using namespace std;
int M, N, L, T;
// depth first search
int dfs(vector<vector<vector<int>>>& g, int l, int x, int y) {
static constexpr int dirs[][3] {{0, -1, 0}, {-1, 0, 0}, {0, 1, 0},
{1, 0, 0}, {0, 0, -1}, {0, 0, 1}};
if (l < 0 || x < 0 || y < 0 || l == L || x == N || y == M || !g[l][y][x])
return 0;
g[l][y][x] = 0; // mark as seen
// int areas = 1;
// for (const auto& d : dirs)
// areas += dfs(g, l + d[2], x + d[0], y + d[1]);
// return areas;
return 1 + dfs(g, l, x - 1, y) // left
+ dfs(g, l, x + 1, y) // right
+ dfs(g, l, x, y - 1) // up (北)
+ dfs(g, l, x, y + 1) // down (南)
+ dfs(g, l + 1, x, y) // 往上爬一层
+ dfs(g, l - 1, x, y); // 往下爬一层
}
int main(void) {
cin >> M >> N >> L >> T; // T 为阈值(yuzhi)我以前一直读成(fazhi)
vector<vector<vector<int>>> g(L, vector<vector<int>>(M, vector<int>(N)));
for (int l = 0; l < L; ++l)
for (int y = 0; y < M; ++y)
for (int x = 0; x < N; ++x)
cin >> g[l][y][x];
int ans = 0;
for (int l = 0; l < L; ++l)
for (int y = 0; y < M; ++y)
for (int x = 0; x < N; ++x)
if (g[l][y][x] == 1) {
const int areas = dfs(g, l, x, y);
if (areas >= T) ans += areas;
}
printf("%d\n", ans);
}
BFS 版
#include <iostream>
#include <queue>
#include <tuple>
#define f(inc, frm, to) for (unsigned inc = frm; inc < to; ++inc)
using namespace std;
const int M = 1300, N = 150, L = 70;
int l, m, n, t;
bool board[L][M][N];
inline int BFS(int sl, int sx, int sy) {
queue<tuple<int, int, int>> q{{{sl, sx, sy}}};
board[sl][sy][sx] = 0;
int dirs[][3] {{0, 0, -1}, {0, -1, 0}, {0, 0, 1}, {0, 1, 0}, {-1, 0, 0}, {1, 0, 0}};
int areas = 0;
while (not q.empty()) {
const auto [level, x, y] = q.front(); q.pop();
++areas;
f(d, 0, 6) {
int nl = level + dirs[d][0], nx = x + dirs[d][1], ny = y + dirs[d][2];
if (not(board[nl][ny][nx])) continue;
q.emplace(nl, nx, ny);
board[nl][ny][nx] = 0;
}
}
return areas;
}
int main(void) {
cin >> m >> n >> l >> t;
f(k, 1, l + 1) f(i, 1, m + 1) f(j, 1, n + 1) cin >> board[k][i][j];
int ans = 0;
f(k, 1, l + 1) {
f(i, 1, m + 1) {
f(j, 1, n + 1) {
if (board[k][i][j]) {
int areas = BFS(k, j, i);
if (areas >= t) ans += areas;
}
}
}
}
printf("%d", ans);
return 0;
}