解题过程的小记录,如有错误欢迎指出。
难度:五星(BFS模板题,需要多复习的题目)
要求找出一个三维0/1组中,块中的个数超过给定的门槛数的总个数,不超过门槛数的1不计数
没有考虑门槛数
#include<iostream>
#include<queue>
using namespace std;
const int maxm = 1300, maxn = 130, maxl = 65;
struct node {
int s;
int x;
int y;
}Node;
int m, n, l, t, ans = 0, tempans;
int slices[maxl][maxm][maxn];//三维01矩阵
bool inq[maxl][maxm][maxn] = { false };
int X[6] = { 0,0,-1,1,0,0 };
int Y[6] = { 1,-1,0,0,0,0 };
int S[6] = { 0,0,0,0,1,-1 };
bool judge(int s,int x,int y) {//判断坐标(s,x,y)是否需要访问
//越界
if (s >= l || s < 0 || x >= m || x < 0 || y >= n || y < 0) return false;
//当前位置为0,或已经入队过
if (slices[s][x][y] == 0 || inq[s][x][y] == true) return false;
//以上都不满足,返回true
return true;
}
void BFS(int s, int x, int y) {
queue<node> q;
Node.s = s, Node.x = x, Node.y = y;
q.push(Node);
inq[s][x][y] = true;
while (!q.empty()) {
node top = q.front();//取出队首元素
q.pop(); //队首元素出队
tempans++;//*****当前块中的个数加1
for (int i = 0; i < 6; i++) { //循环6次,得到6个相邻位置
int newS = top.s + S[i];
int newX = top.x + X[i];
int newY = top.y + Y[i];
if (judge(newS, newX, newY)) {//如果新位置可以访问
Node.s = newS, Node.x = newX, Node.y = newY;
q.push(Node); //将新赋值的结点Node加入队列
inq[newS][newX][newY] = true;//将新位置设置为已加入过队列
}
}
}
if (tempans >= t) ans += tempans;//如果当前块中的个数超过要求的门槛值,则计入结果
}
int main()
{
scanf("%d%d%d%d", &m, &n, &l, &t);
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
scanf("%d", &slices[i][j][k]);
}
}
}
for (int i = 0; i < l; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
if (slices[i][j][k] == 1 && inq[i][j][k] == false) {//如果当前位置为1,且未被访问过,则作为BFS的当前块
tempans = 0;//每一块枚举前一定要归零
BFS(i, j, k);
}
}
}
}
printf("%d", ans);
return 0;
}
全部代码因版权原因不放出来,大家可以自行去柳神博客购买或者参考晴神的上机笔记~
本篇代码就是参考晴神的代码写的(看了下柳神和晴神方法一致)
本文地址:https://blog.csdn.net/weixin_41490207/article/details/107341711
如对本文有疑问, 点击进行留言回复!!
springcloud中feign调用处理mybatis-plus Ipage反序列化问题。
Flume 史上最全面的大数据学习第十篇(一) 别再说不知道flume是什么了
网友评论