暴力搜索 | BFS

参考：《算法笔记》

广度优先搜索 breadth first search

• 以广度为第一关键词
• 碰到分叉口，总是依次访问从该分叉口能直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点……
• 如同水花荡开（按层次遍历，从初始点到某结点的最少步数即层数）
• 借助队列实现：分叉口结点出队，与之直接相连的结点入队
• ⚠️已入队过的结点要标记为已入队，不可重复入队。

题目

1091 Acute Stroke (30 分)

题目描述

思路

• 可走的路：L * M * N矩阵中1结点到与之“相邻”1结点
• BFS：找到矩阵中为1的结点（未访问过），以它为起点搜寻它相邻的1结点（标记为访问过），并计数1的结点个数。若大于等于阈值，则计入，否则丢弃。找下一个未访问过的1结点，继续……
• ⚠️传参顺序，（z，x，y）要留意

#include <cstdio>
#include <queue>

using namespace std;
int MM, NN, LL, TH;
bool graph[60][130][1290] = {false}, visited[60][130][1290] = {false};

struct Node {
    int z, x, y;
};
int x_offsets[6] = {1, -1, 0, 0, 0, 0};
int y_offsets[6] = {0, 0, 1, -1, 0, 0};
int z_offsets[6] = {0, 0, 0, 0, 1, -1};

int BFS(int layer, int i, int j) {
    int sum = 1;
    visited[layer][j][i] = true;
    queue<Node> mq;
    mq.push(Node{layer, i, j});
    while (!mq.empty()) {
        Node curr_node = mq.front();
        mq.pop();
        for (int k = 0; k < 6; ++k) {
            int x = curr_node.x + x_offsets[k], y = curr_node.y + y_offsets[k], z = curr_node.z + z_offsets[k];
            if (x < 0 || x >= NN || y < 0 || y >= MM || z < 0 || z >= LL)
                continue;
            if (!visited[z][y][x] && graph[z][y][x]) {
                sum++;
                visited[z][y][x] = true;
                mq.push(Node{z, x, y});
            }
        }
    }
    return sum;
}

int main() {
    scanf("%d%d%d%d", &MM, &NN, &LL, &TH);
    int value;
    for (int i = 0; i < LL; ++i) {
        for (int j = 0; j < MM; ++j) {
            for (int k = 0; k < NN; ++k) {
                scanf("%d", &value);
                if (value) graph[i][j][k] = true;
            }
        }
    }
    int total = 0;
    for (int i = 0; i < LL; ++i) {
        for (int j = 0; j < MM; ++j) {
            for (int k = 0; k < NN; ++k) {
                if (graph[i][j][k] && !visited[i][j][k]) {
                    int curr = BFS(i, k, j);
                    if (curr >= TH)
                        total += curr;
                }
            }
        }
    }
    printf("%d\n", total);
    return 0;
}