题意：
给你一个正长方体，长宽高分别为n、m、k,这个长方体由n*m*k个1*1*1的小立方体组成
把这些小立方体编号为0-(n*m*k-1),
再给l个编号，表示这些小立方体是存在的，否则就是不存在的
求最总整个图形的外表面积
解题思路：
首先解决坐标与编号的转换，用0开始标号，比用1方便很多，跟二维数组差不多，很轻松就可以推出
坐标转编号：id=z*(m*n)+y*n+x;
编号转坐标：
z=id/(n*m);
id-=z*(m*n);
y=id/n;
x=id%n;
上面写成两个函数备用
首先想到，以其中一个存在的小立方体开始，往上下左右前后六个方向搜索，如果这个方向上有小方块，就转移到这个小方块上继续搜索
如果没有，则表面积+1
但是这个方法求出来的包含内表面积，比如第二个样例会输出60，想不到方法能减去
我们在原长方体的周围包上一圈不存在的小立方体
然后再按上面的方法改成搜索“不存在的小立方体”，只搜索最外圈，那么我们得到的结果就是最外圈那些“不存在的小立方体”所构成的部分的内外表面积之和
它的内表面积就是我们要求的“存在的小立方体组成的物体”的外表面积了。
而它的外表面积就是(n*m+m*k+n*k)*2,其实可以不用算，在搜索的时候如果是边界不用+1就行了。
注意要用BFS，DFS会栈溢出。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define pb(a) push_back(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r void debug() { #ifdef ONLINE_JUDGE #else freopen("d:\in.txt","r",stdin); // freopen("d:\out1.txt","w",stdout); #endif } char getch() { char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } struct point { int x,y,z; }; int n,m,k,l; int show[270000];//记录该位置是否存在 int vis[270000];//访问标记 int dx[]={0,0,-1,1,0,0}; int dy[]={0,0,0,0,-1,1}; int dz[]={1,-1,0,0,0,0}; int num; int toid(int x,int y,int z,int n,int m,int k) //两个互转的函数 { return z*(m*n)+y*n+x; } void topoint(int id,int &x,int &y,int &z,int n,int m,int k) { z=id/(n*m); id-=z*(m*n); y=id/n; x=id%n; } int bfs(int idx) { queue<int> q; q.push(idx); while(!q.empty()) { int id=q.front();q.pop(); if(vis[id])continue; vis[id]=1; int x,y,z; topoint(id,x,y,z,n,m,k); for(int d=0;d<6;d++) { int nx=x+dx[d]; int ny=y+dy[d]; int nz=z+dz[d]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&nz>=0&&nz<k) { int nid=toid(nx,ny,nz,n,m,k); if(!show[nid]) //如果新位置空白，则继续搜索 { if(!vis[nid]) q.push(nid); }else //否则就是多了一个面 num++; } } } return 0; } int main() { // debug(); while(scanf("%d%d%d%d",&n,&m,&k,&l)!=EOF&&(n||m||k||l)) { memset(show,0,sizeof(show)); for(int i=1;i<=l;i++) { int x; scanf("%d",&x); //转化成新的编号 int a,b,c; topoint(x,a,b,c,n,m,k); x=toid(a+1,b+1,c+1,n+2,m+2,k+2); show[x]=1; } n+=2;m+=2;k+=2; memset(vis,0,sizeof(vis)); num=0; bfs(0); //从最外圈的随便一个开始 printf("The number of faces needing shielding is %d. ",num); } return 0; }