1091. Acute Stroke (30)[bfs广度优先搜索+种子填充]

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1091

2. 思路：

3. 源码：

#include<iostream>#include<queue>using namespace std;int G[1286][128][60] = { 0 };//矩阵的三维表示。分别为行， 列及层次int M, N, L, T;//分别为行数， 列数， 层数及阈值。int cnt = 0;//累计符合要求的结点int direct_x[6] = { -1, 1, 0, 0, 0, 0 };//x方向的偏移，下同int direct_y[6] = { 0, 0, -1, 1, 0, 0 };int direct_z[6] = { 0, 0, 0, 0, -1, 1 };struct Node{	Node(int a, int b, int c) : x(a), y(b), z(c) {}	int x, y, z;//用数组的下标表示结点的坐标};void bfs(int a, int b, int c);//bfs广度优先int main(void){	//freopen("in.txt", "r", stdin);	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", &G[i][j][k]);//注意这里的顺序，可理解为x,y, z坐标		}	}	for (int k = 0; k < L; k++)//因为不是强连通图，还需要加循环，进行bfs	{		for (int i = 0; i < M; i++)		{			for (int j = 0; j < N; j++)			{				if (G[i][j][k] == 1)					bfs(i, j, k);			}		}	}	printf("%d/n", cnt);	return 0;}void bfs(int a, int b, int c){	queue<Node> Q;	Q.push(Node(a, b, c));//入队	int cur_cnt = 1;	G[a][b][c] = 0;//标记该点已遍历	while (!Q.empty())	{		Node tem = Q.front();		Q.pop();		G[tem.x][tem.y][tem.z] = 0;				for (int i = 0; i < 6; i++)//此处的6个方向可以用if判断，不过数组简单些		{			int newc = tem.z + direct_z[i];			int newa = tem.x + direct_x[i];			int newb = tem.y + direct_y[i];			if ((newa < 0 || newa >= M) || (newb < 0 || newb >= N)//已出界				|| (newc < 0 || newc >= L))				continue;			if (G[newa][newb][newc] == 0)//已访问或无效点				continue;			cur_cnt++;//访问新的结点			G[newa][newb][newc] = 0;			Q.push(Node(newa, newb, newc));		}	}	if (cur_cnt >= T)		cnt += cur_cnt;//累计	return;}