盲目搜索 – BFS思想及其应用

PAT-A1091

典型的搜索标记问题，需要考虑到过高的递归深度 栈溢出 问题，因此选用BFS策略

---

(¬､¬) Q：这一看就是搜索嘛…我又来啃老本了，又是摸鱼的一天

( ˙灬˙ ) A：噢，是嘛？宁用DFS给我做一个看看…

Σ(っ °Д °;)っ Q：卧槽？最后两个样例段错误什么鬼，我板儿逼保证数组没越界！

╮(๑•́ ₃•̀๑)╭ A：宁忘记了递归深度，这个深度可达 $\scriptsize maxL \times maxM \times maxN \sim 10^8$ 的，巨大的栈开销，再高能的机器也吃不消啊，这就是迭代的优越性咯，要用BFS的哥

( ∙̆ .̯ ∙̆ ) Q：等下，这个插图怎么这么诡异，这是三维插图嘛，三维立方体有……19个邻接方块？这个前进方向得写累死。

(-_-メ) A：盲生，你发现了华点！你成功将题的难度转移到了题意理解上！这个图的意思：相邻像素指的是上下左右前后=。=想不到吧……它不是你想象中的那种三维扫描方块，尊重题意

(@-～-@) A：哦对了，有个小坑注意别踩，三维数组一定按层数L、长M、宽N顺序声明和访问，别给了输入顺序就顺手了

---

#include <iostream>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

struct coordinate {
    int x, y, z;
};

const int maxM = 1286, maxN = 128, maxL = 60;
int cube[maxL][maxM][maxN];
int cnt = 0, total = 0;
int M, N, L, T;
queue<coordinate> q;

void BFS(int i, int j, int k) {
    q.push({i, j, k});
    int x, y, z;
    while (!q.empty()) {
        coordinate co = q.front();
        q.pop();
        x = co.x; y = co.y; z = co.z;
        if (x < 0 || x == L || y < 0 || y == M || z < 0 || z == N)
            continue;

        int val = cube[x][y][z];
        if (val == 0) continue;
        if (val == 1) {
            cnt++;
            cube[x][y][z] = 0;
            q.push({x + 1, y, z});
            q.push({x - 1, y, z});
            q.push({x, y + 1, z});
            q.push({x, y - 1, z});
            q.push({x, y, z + 1});
            q.push({x, y, z - 1});
        }
    }
}

int main() {
    scanf("%d%d%d%d", &M, &N, &L, &T);
    memset(cube, 0, sizeof(cube));
    for (int i = 0; i < L; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < N; k++)
                scanf("%d", &cube[i][j][k]);

    for (int i = 0; i < L; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < N; k++)
                if (cube[i][j][k] != -1) {
                    cnt = 0;
                    BFS(i, j, k);
                    if (cnt >= T) total += cnt;
                }

    printf("%d\n", total);

    return 0;
}