PAT A1091——BFS
One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M×N matrix, and the maximum resolution is 1286 by 128); L (≤60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).
Then L slices are given. Each slice is represented by an M×N matrix of 0's and 1's, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1's to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.
Figure 1
Output Specification:
For each case, output in a line the total volume of the stroke core.
Sample Input:
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0
Sample Output:
26
题意：
给出一个三维矩阵，数组元素的取值为0或1.与某一个相邻的元素为其上、下、左、右、前、后这6个方向的邻接元素。另外，若干个相邻的“1”称为一个“块”(不必两两相邻，只要与块中某一个“1”
相邻该“1”就在块中）。而如果某个块中的“1”的个数不低于T个，那么称则个块为“卒中核心区”。现在需要求解所有卒中核心区中的1的个数之和。
1 #include<cstdio>
2 #include<queue>
3 using namespace std;
4 struct node {
5 int x,y,z; //位置(x,y,z)
6 }Node;
7 int n,m,slice,T; //矩阵为n*m,共有slice层，T为卒中核心区中1的个数的下限
8 int pixel[1290][130][61]; //三维01矩阵
9 bool inq[1290][130][61] = {false}; //记录位置(x,y,z)是否已入过队
10 int X[6] = {0,0,0,0,1,-1}; //增量矩阵
11 int Y[6] = {0,0,1,-1,0,0};
12 int Z[6] = {1,-1,0,0,0,0};
13
14 bool judge(int x,int y,int z) { //判断坐标(x,y,z)是否需要访问
15 //越界返回false
16 if(x>=n || x<0 || y>=m || y<0 || z>=slice || z<0) return false;
17 //若当前位置为0或(x,y,z)已入过队，则返回false
18 if(pixel[x][y][z] == 0 || inq[x][y][z] == true) return false;
19 //以上都不满足，返回true
20 return true;
21 }
22
23 //BFS函数访问位置(x,y,z)所在的块，将该块中所有“1”的inq都设置为true
24 int BFS(int x,int y,int z) {
25 int tot = 0; //计数当前块中1的个数
26 queue<node> Q; //定义队列
27 Node.x = x,Node.y = y,Node.z = z; //结点Node的位置为(x,y,z)
28 Q.push(Node); //将结点Node入队
29 inq[x][y][z] = true; //设置位置(x,y,z)已入过队
30 while(!Q.empty()) {
31 node top = Q.front(); // 取出队首元素
32 Q.pop(); //队首元素出队
33 tot++; //当前块中1的个数加1
34 for(int i=0; i<6; i++) { //循环6次，得到6个增量方向
35 int newX = top.x + X[i];
36 int newY = top.y + Y[i];
37 int newZ = top.z + Z[i];
38 if(judge(newX,newY,newZ)) { //新位置(newX,newY,newZ)需要访问
39 //设置Node的坐标
40 Node.x = newX,Node.y = newY,Node.z = newZ;
41 Q.push(Node); //将结点Node入队
42 inq[newX][newY][newZ] = true; //设置(newX,newY,newZ)已入过队
43 }
44 }
45 }
46 if(tot >= T) return tot; //如果超过阈值，则返回
47 else return 0; //否则不记录该块1的个数
48 }
49
50 int main(){
51 scanf("%d%d%d%d",&n,&m,&slice,&T);
52 for(int z = 0; z<slice; z++) { //注意先枚举切片层号
53 for(int x = 0; x<n; x++) {
54 for(int y = 0; y<m; y++) {
55 scanf("%d",&pixel[x][y][z]);
56 }
57 }
58 }
59 int ans = 0; //记录卒中核心区中1的个数总和
60 for(int z = 0; z<slice; z++) {
61 for(int x=0; x<n; x++) {
62 for(int y = 0; y<m; y++) {
63 //如果当前位置为1，且未被访问，则BFS当前块
64 if(pixel[x][y][z] == 1 && inq[x][y][z] == false) {
65 ans += BFS(x,y,z);
66 }
67 }
68 }
69 }
70 printf("%d\n",ans);
71 return 0;
72 }
最新文章
- appium案例
- Spring知识点总结大全（2）
- 【转载】C++中public,protected,private访问
- all things are difficult before they are easy
- Java基础之处理事件——使用适配器类（Sketcher 3 using an Adapter class)
- SOCKET 地址
- linux 防火墙打开端口/屏蔽IP等
- netty httpserver
- 射频识别技术漫谈(5)——防冲突【worldsing 笔记】
- POJ2914
- parcel write boolean值
- Long-Polling, Websockets, SSE(Server-Sent Event), WebRTC 之间的区别
- Python的hasattr() getattr() setattr() 函数使用方法详解 (转)
- SpringCloud微服务高级
- Maven包下载不下来的情况
- hdu3826-Squarefree number-(欧拉筛+唯一分解定理)
- char与TCHAR相互转换（拒绝中文乱码，好用！）
- table边框
- python语法学习之函数、类、模块
- 区分IE8/IE7/IE6及其他浏览器-CSS “\9″