題目描述：
問一個由1*1*1的立方體組成的空間形狀的外表面積。
http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1&search=true&firstId=-1&lastId=-1&problemCode=&handle=hanfei19910905&idStart=&idEnd=
算法分析：
想像從“無窮遠”向中間搜索， 一個立方體一個立方體的搜， 就可以了。
zoj 1063
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<queue>
6 using namespace std;
7 const int V = 65;
8 bool vis[V][V][V],num[V][V][V];
9 int n,m,h;
10 struct node{int x,y,z;node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}};
11 queue<node>Q;
12 inline bool fit(int x,int y,int z) {
13 return x <= n && x >= 0 && y <=m && y>=0 && z <= h && z >=0 ;
14 }
15 int bfs() {
16 // static int debug[V*V*V], len = 0;
17 // len = 0;
18 Q.push(node(0,0,0));
19 vis[0][0][0] = 1;
20 int ans = 0;
21 while(!Q.empty()){
22 node p = Q.front();
23 Q.pop();
24 for(int i = 0; i < 6; i++) {
25 int x = p.x + (i == 0) - (i == 1);
26 int y = p.y + (i == 2) - (i == 3);
27 int z = p.z + (i == 5) - (i == 4);
28 if(fit(x,y,z)) {
29 if(!vis[x][y][z] && !num[x][y][z]) {
30 vis[x][y][z] = 1;
31 Q.push(node(x,y,z));
32 }
33 else if(num[x][y][z]){
34 ans ++;
35 // debug[len ++] = x + y * V + z * V * V;
36 }
37 }}}
38 // sort(debug,debug+len);
39 // for(int i = 0; i < len; i++) cout<< debug[i]/(V*V) <<" "<<debug[i] %(V*V) / V <<" "<<debug[i] %V<<endl;;
40 return ans;
41 }
42 int main(){
43 int t,v;
44 while(~scanf("%d%d%d%d",&n,&m,&h,&t)&&n) {
45 memset(num,0,sizeof(num));
46 memset(vis,0,sizeof(vis));
47 while(t --) {
48 scanf("%d",&v);
49 int z= v / (n*m);
50 int y = v % (n*m) / n;
51 int x = v % (n*m) % n;
52 x++,y++,z++;
53 // cout<<x<<" "<<y<<" "<<z<<endl;
54 num[x][y][z] =1;
55 }
56 n++,m++,h++;
57 printf("The number of faces needing shielding is %d.\n",bfs());
58 }
59 return 0;
60 }
61 posted on 2012-09-10 11:33
西月弦 閱讀(232)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告