关于算法-数据结构: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;
}