关于算法-数据结构:PAT甲级1091-Acute-Stroke

题目粗心：

给定一个三维数组,数组元素的取值为0或者1,与某一元素相邻的元素是上下左右前后6个方向的元素,如果有若干个1相邻,那么就称这些1所组成的区域为一个块,如果块中1的个数不低于T个,那就称这个块为stroke core,当初要求计算所有stroke core的1个累计个数.

算法思路：

这里的块实际上和咱们常见的图外面的连通重量的概念很类似,首先想到的就是遍历这个3维矩阵的每一个连通块,而后计算非法的每个连通块的1的个数(大于等于T),这里咱们采纳邻接矩阵存储这个3维图像,留神到一点,咱们遍历中邻接点的地位为上下左右前后6个方向,那么咱们就只须要每次往则6个方向后退一格就好,应用增量矩阵$incrementOfX$,$incrementOfY$,$incrementOfZ$对以后地位x,y,z进行加减取得下一个结点的地位.咱们能够采纳BFS的思维来进行解决(用DFS有可能会导致段谬误)，首先，每次抉择进行BFS的终点都是没有入队并且为数字1的点，入队终点后，在BFS的搜寻过程中，只有队列不空，出队队首节点,应用$count$统计以后连通块1的个数(队列中的节点都是数字为1的点)，而后将6个领接方向的点中没有越界，数字为1并且没有退出队列的节点进行入队操作，循环完结时就返回$count$。最初应用$volumeOfStrokeCore$累计所有$count>=T$的$count$即可。

留神点：

• 1、将多维数组写在main办法之外，能够主动赋初始值，节约工夫，避免段谬误。
• 2、应用DFS会呈现最初2个测试点段谬误。

提交后果：

AC代码：

#include <cstdio>
#include <queue>

using namespace std;

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

int image[1290][130][70];
bool isQueued[1290][130][70];// x,y,z地位的元素是否曾经入队
int incrementOfX[6] = {0,0,0,0,1,-1};
int incrementOfY[6] = {0,0,1,-1,0,0};
int incrementOfZ[6] = {1,-1,0,0,0,0};
int M,N,L,T;// 长宽高和阈值

queue<Position> q;

// 判断x,y,z是否有必要拜访
bool isQualified(int x,int y,int z){
    // 如果越界，则不再查问
    if(x>=M||x<0||y>=N||y<0||z>=L||z<0) return false;
    // 0不拜访，曾经入队的不拜访
    return !(image[x][y][z] == 0 || isQueued[x][y][z]);
}

int BFS(int x,int y,int z){
    int count = 0;//以后连通块1的个数
    Position p{x,y,z};
    q.push(p);
    isQueued[x][y][z] = true;
    while (!q.empty()){
        // 队首元素出队
        p = q.front();
        q.pop();
        ++count;
        // 枚举6个方向的领接点
        for (int i = 0; i < 6; ++i) {
            int X = p.x+incrementOfX[i];
            int Y = p.y+incrementOfY[i];
            int Z = p.z+incrementOfZ[i];
            if(isQualified(X,Y,Z)){
                Position t{X,Y,Z};
                q.push(t);
                isQueued[X][Y][Z] = true;
            }
        }
    }
    return count;
}

int main()
{
    scanf("%d %d %d %d",&M,&N,&L,&T);
    for (int k = 0; k < L; ++k) {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                scanf("%d",&image[i][j][k]);
            }
        }
    }
    int volumeOfStrokeCore = 0;
    for (int k = 0; k < L; ++k) {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                // 遍历每一个元素
                if(image[i][j][k]==1&&!isQueued[i][j][k]){
                    // 只有以后元素为1，并且没有退出到队列之中
                    int countOne = BFS(i,j,k);//取得以后连通块中的个数
                    if(countOne>=T){
                        volumeOfStrokeCore += countOne;
                    }
                }
            }
        }
    }
    printf("%d",volumeOfStrokeCore);
    return 0;
}