PAT甲级A1091---广度优先搜索

1091 Acute Stroke (30分)

分析：

给出一个三维数组，若干个相邻的“1”称为一个块。如果某个块中“1”的个数不低于T个，则这个块称为“卒中核心区”。现在需要求解所有卒中核心区中的1的个数之和。
枚举三维数组每一个位置，如果为0，则跳过；如果为1，则使用bfs查询与该位置相邻的6个位置。

C++：

#include <cstdio>
#include <queue>

using namespace std;

struct Node {
    int x, y, z;
} temp;

int n, m, slice, T;//n*m矩阵，共有slice层，T为卒中核心区1的个数下限
int pixel[1290][130][61];
bool inq[1290][130][61];
int X[6] = {0, 0, 0, 0, 1, -1};
int Y[6] = {0, 0, 1, -1, 0, 0};
int Z[6] = {1, -1, 0, 0, 0, 0};

bool judge(int x, int y, int z) {
    if (x >= n || x < 0 || y >= m || y < 0 || z >= slice || z < 0) {
        return false;
    }
    if (pixel[x][y][z] == 0 || inq[x][y][z] == true) {
        return false;
    }
    return true;
}

int bfs(int x, int y, int z) {
    int cnt = 0;//当前块1的个数
    queue<Node> q;
    temp.x = x;
    temp.y = y;
    temp.z = z;
    q.push(temp);
    inq[x][y][z] = true;
    while (!q.empty()) {
        Node top = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < 6; i++) {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            int newZ = top.z + Z[i];
            if (judge(newX, newY, newZ) == true) {
                temp.x = newX;
                temp.y = newY;
                temp.z = newZ;
                q.push(temp);
                inq[newX][newY][newZ] = true;
            }
        }
    }
    if (cnt >= T) {
        return cnt;
    } else {
        return 0;
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &slice, &T);
    for (int z = 0; z < slice; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                scanf("%d", &pixel[x][y][z]);
            }
        }
    }
    int res = 0;
    for (int z = 0; z < slice; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (pixel[x][y][z] == 1 && inq[x][y][z] == false) {
                    res += bfs(x, y, z);
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}