[ACM_搜索] POJ 1096 Space Station Shielding （搜索 + 洪泛算法Flood

[ACM_搜索] POJ 1096 Space Station Shielding （搜索 + 洪泛算法Flood_Fill）

Description

Roger Wilco is in charge of the design of a low orbiting space station for the planet Mars. To simplify construction, the station is made up of a series of Airtight Cubical Modules (ACM's), which are connected together once in space. One problem that concerns Roger is that of (potentially) lethal bacteria that may reside in the upper atmosphere of Mars. Since the station will occasionally fly through the upper atmosphere, it is imperative that extra shielding be used on all faces of the ACM's touch, either edge to edge or face to face, that joint is sealed so no bacteria can sneak through. Any face of an ACM shared by another ACM will not need shielding, of course, nor will a face which cannot be reached from the outside. Roger could just put extra shielding on all of the faces of every ACM, but the cost would be prohibitive. Therefore, he wants to know the exact number of ACM faces which need the extra shielding.

Input

Input consists of multiple problem instances. Each instance consists of a specification of a space station. We assume that each space station can fit into an n x m x k grid (1 <= n, m, k <= 60), where each grid cube may or may not contain an ACM. We number the grid cubes 0, 1, 2, ..., kmn-1 as shown in the diagram below. Each space station specification then consists of the following: the first line contains four positive integers n m k l, where n, m and k are as described above and l is the number of ACM's in the station. This is followed by a set of lines which specify the l grid locations of the ACM's. Each of these lines contain 10 integers (except possibly the last). Each space station is fully connected (i.e., an astronaut can move from one ACM to any other ACM in the station without leaving the station). Values of n = m = k = l = 0 terminate input.

Output

For each problem instance, you should output one line of the form

The number of faces needing shielding is s.

Sample Input

2 2 1 3
0 1 3
3 3 3 26
0 1 2 3 4 5 6 7 8 9
10 11 12 14 15 16 17 18 19 20
21 22 23 24 25 26
0 0 0 0

Sample Output

The number of faces needing shielding is 14.
The number of faces needing shielding is 54.

Source

East Central North America 2001

题目大意：给你一个正长方体，长宽高分别为n、m、k,这个长方体由n*m*k个1*1*1的小立方体组成，把这些小立方体编号为0-(n*m*k-1),再给l个编号，表示这些小立方体是存在的，否则就是不存在的。求最总整个图形的外表面积。

解题思路：首先想到，以其中一个存在的小立方体开始，往上下左右前后六个方向搜索，如果这个方向上有小方块，就转移到这个小方块上继续搜索，如果没有，则表面积+1，但是这个方法求出来的包含内表面积！！！于是采用反向思维，在这个立方体周围包一层不存在立方体(这里的不存在就是标记该位置单位立方体tab[i][j][k]=0,存在为1），然后再按上面的方法改成搜索“不存在的小立方体”，只搜索最外圈，那么我们得到的结果就是最外圈那些“不存在的小立方体”所构成的部分的内外表面积之和，它的内表面积就是我们要求的“存在的小立方体组成的物体”的外表面积了。而它的外表面积就是(n*m+m*k+n*k)*2,其实可以不用算，在搜索的时候如果是边界不用+1就行了。注意要用BFS，刚开始用DFS栈溢出了。

知识扩展：这题是标准的洪泛算法的题目，记得勘测油田的那道简单搜索题吗？还有某些画图软件上的把图像上相连的某种颜色换成其他的，你点一块其他全部变化啦。这些都是洪泛算法的应用。本题意思是有一个由单位立方体组成的长方体，有些单位立方体内有宇航员，而外太空的毒气可以渗入没有贴防护膜的房间，所以要在某些必要的位置贴防护膜来防止毒气进入太空站空间。

相关链接：维基百科——洪泛算法：http://zh.wikipedia.org/zh-cn/Flood_fill

图像处理之泛洪填充算法(Flood Fill Algorithm) ：http://blog.csdn.net/jia20003/article/details/8908464

洪泛算法讲解：http://www.nocow.cn/index.php/Flood_Fill

 1 #include<iostream>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 int n,m,k,l;
 6 bool tab[70][70][70],visit[70][70][70];
 7 int face_num;
 8 class W3{
 9 public:
10     int x,y,z;
11     W3& set(int xx,int yy,int zz){
12         x=xx;y=yy;z=zz;
13         return *this;
14     }
15 };
16 void bfs(){
17     face_num=0;
18     queue<W3> Q;
19     W3 temp;
20     Q.push(temp.set(0,0,0));
21     while(!Q.empty()){
22         W3 Top=Q.front();Q.pop();
23         if(visit[Top.x][Top.y][Top.z])continue;
24         visit[Top.x][Top.y][Top.z]=1;
25         if(Top.x-1>=0){
26             if(tab[Top.x-1][Top.y][Top.z]==0){
27                 if(!visit[Top.x-1][Top.y][Top.z])Q.push(temp.set(Top.x-1,Top.y,Top.z));
28             }
29             else face_num++;
30         }//左走一格
31         if(Top.x<=n){
32             if(tab[Top.x+1][Top.y][Top.z]==0){
33                 if(!visit[Top.x+1][Top.y][Top.z])Q.push(temp.set(Top.x+1,Top.y,Top.z));
34             }
35             else face_num++;
36         }//右走一格
37         if(Top.y-1>=0){
38             if(tab[Top.x][Top.y-1][Top.z]==0){
39                 if(!visit[Top.x][Top.y-1][Top.z])Q.push(temp.set(Top.x,Top.y-1,Top.z));
40             }
41             else face_num++;
42         }//后走一格
43         if(Top.y<=m){
44             if(tab[Top.x][Top.y+1][Top.z]==0){
45                 if(!visit[Top.x][Top.y+1][Top.z])Q.push(temp.set(Top.x,Top.y+1,Top.z));
46             }
47             else face_num++;
48         }//前走一格
49         if(Top.z-1>=0){
50             if(tab[Top.x][Top.y][Top.z-1]==0){
51                 if(!visit[Top.x][Top.y][Top.z-1])Q.push(temp.set(Top.x,Top.y,Top.z-1));
52             }
53             else face_num++;
54         }//下走一格
55         if(Top.z<=k){
56             if(tab[Top.x][Top.y][Top.z+1]==0){
57                 if(!visit[Top.x][Top.y][Top.z+1])Q.push(temp.set(Top.x,Top.y,Top.z+1));
58             }
59             else face_num++;
60         }//上走一格
61     }
62 }
63 int main(){
64     while(cin>>n>>m>>k>>l){
65         if(!n && !m && !k && !l)break;
66         memset(tab,0,sizeof(tab));
67         memset(visit,0,sizeof(visit));
68         int temp1;
69         for(int i=0;i<l;i++){
70             cin>>temp1;
71             tab[temp1%(m*n)%n+1][temp1%(m*n)/n+1][temp1/(n*m)+1]=1;
72         }//输入数据并转换为tab[][][]的3维矩阵(这里从1,1,1开始,最外层相当于无人方块)
73         bfs();
74         cout<<"The number of faces needing shielding is "<<face_num<<".
";
75     }return 0;
76 }