1091 Acute Stroke (30分)(经典BFS的问题）

BFS的题目可以用来求解两种经典的问题，一种是求矩阵中连续块的数量，另一种是求走出迷宫所需的最小的步数，这两种应用都有着挺明显的套路，在掌握其基本思想的基础上，可以灵活的解决相应的变形的题目

题目描述如下：


题目大致意思：
脑子由薄片组成，MxN是一片薄片的长与宽，L是片数，T是单个中风核心的体积的阈值。

//若三维矩阵中有若干个邻接的像素1，则这些像素1构成了1块中风核心。

可能出现多个中风核心区域，必须满足条件：单个体积>=T，求中风核心的总体积之和。
大致思路：
这个题目跟算法笔记中求一个矩阵中连续的1的块数的题属于同一种题，基本思想是一样的，使用广度优先遍历，用队列来实现。
提交结果如下：

提交的代码如下：

#include<iostream>
#include<queue>
using namespace std;
int m,n,l,t;
int arr[60][1286][128];
bool inq[60][1286][128]={false};
int X[6]={0,0,0,0,1,-1};
int Y[6]={0,0,1,-1,0,0};
int Z[6]={1,-1,0,0,0,0};
struct Node
{int z,x,y;
};
queue<Node> Q;
int BFS(int z,int x,int y);
bool is_ok(int z,int x,int y)
{if(x>=m||y>=n||z>=l||x<0||y<0||z<0)return false;if(arr[z][x][y]==0||inq[z][x][y]==true)return false;return true;
}
int main()
{int ans=0;cin>>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++)cin>>arr[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(arr[i][j][k]==1&&inq[i][j][k]==false){int temp=BFS(i,j,k);if(temp>=t)ans+=temp;}}cout<<ans<<endl;
}
int BFS(int z,int x,int y)
{Node node;node.z=z;node.x=x;node.y=y;Q.push(node);inq[z][x][y]=true;int temp=1;while(!Q.empty()){Node top=Q.front();Q.pop();for(int i=0;i<6;i++){int new_z=top.z+Z[i];int new_x=top.x+X[i];int new_y=top.y+Y[i];if(is_ok(new_z,new_x,new_y)){temp++;Node new_node;new_node.z=new_z;new_node.x=new_x;new_node.y=new_y;Q.push(new_node);inq[new_z][new_x][new_y]=true;}}}return temp;
}

本次提交后累计得分为1387。