共计 1885 个字符,预计需要花费 5 分钟才能阅读完成。
题目粗心:
给定一个三维数组, 数组元素的取值为 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;
}
正文完