【PAT甲级】1091 Acute Stroke (30分)

解题过程的小记录，如有错误欢迎指出。

难度：五星（BFS模板题，需要多复习的题目）

题目分析

要求找出一个三维0/1组中，块中的个数超过给定的门槛数的总个数，不超过门槛数的1不计数

注意点

1. 一旦有push的行为，对应的inq数列一定要更改为true
2. 要超过门槛数的1才可以计入总数
3. 队列中的数在出列的时候才计数（出列说明它一定在块当中）

我的解题过程

思路

1. 建立一个三维数组保存0/1信息，建立node结构体用于后面把坐标加入队列
2. 建立inq三维数组用于保存对应的坐标是否入过队列，如果入过就不需要再入
3. 写一个judge函数用于判断某个坐标的上下左右前后点是否合法（有无越界或者已经入过队列或者不为1）
4. 写BFS函数，搜查块中的1数，如果超过门槛数则计入结果

bug

没有考虑门槛数

代码

#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;
}

dalao的代码

全部代码因版权原因不放出来，大家可以自行去柳神博客购买或者参考晴神的上机笔记~

借鉴点

本篇代码就是参考晴神的代码写的（看了下柳神和晴神方法一致）

本文地址：https://blog.csdn.net/weixin_41490207/article/details/107341711