读书人

Cube - 一路题不知道错在哪 (代码贴

发布时间: 2013-07-16 22:38:04 作者: rapoo

Cube --- 一道题,不知道错在哪 (代码贴出)
题目描述
在一个三维空间中有N个立方体(不一定为正方体,也可能是长方体),

第i个立方体占据xi1,yi1, zi1 --- xi2, yi2, zi2的位置。

这N个立方体可能有相交,也可能重叠(即有可能有公共体积或公共面积)。这N个立方体构成一个大的几何图形。现在求这个几何图形的外表面积。

输入格式
第一行,一个整数N,表示立方体的个数。

第二行至第N+1行,每行6个用空格隔开的整数,分别表示x_{i1},y_{i1}, z_{i1}, x_{i2}, y_{i2}, z_{i2}
输出格式
一行,一个整数,表示外表面积的大小。

Sample Input

1
0 0 0 1 1 1

Sample Output
6

Sample Explain
   +___+
/ /|
+___+ |
| | +
| |/
+___+

About Testdata
40% 1<=N<=10

100% 1<=N<=200,0<=xi1,yi1,zi1,xi2,yi2,zi2<=200,xi1<xi2,yi1<yi2,zi1<zi2


Limits
Time limit: 1000ms, memory limit: 50000kb.

我写的代码是

#include <iostream>
#include <stdlib.h>
using namespace std;

int n,i,j,k,l,x11,y11,z11,x22,y22,z22,a,b,c;
int cnt=0;
int space[205][205][205]={0};

int main(){
cin>>n;
for (l=0;l<n;++l){
cin>>x11>>y11>>z11>>x22>>y22>>z22;
for (i=x11+1;i<=x22;++i)
for (j=y11+1;j<=y22;++j)
for (k=z11+1;k<=z22;++k)
space[i][j][k]=1;
}

for (i=1;i<205;++i)
for (j=1;j<205;++j)
for (k=0;k<205;++k){
if (space[i][j][k]==1){
if (space[i+1][j][k]==0) cnt++;
if (space[i-1][j][k]==0) cnt++;
if (space[i][j+1][k]==0) cnt++;
if (space[i][j-1][k]==0) cnt++;
if (space[i][j][k+1]==0) cnt++;
if (space[i][j][k-1]==0) cnt++;
}
}
cout<<cnt<<endl;
}


结果是有5个wrong answer:

Judging... PROB=3041 LANG=C++

Accepted (Time: 40ms, Memory: 38272kb)
Accepted (Time: 30ms, Memory: 38272kb)
Accepted (Time: 30ms, Memory: 38272kb)
Accepted (Time: 20ms, Memory: 38272kb)
Wrong Answer (Time: 140ms, Memory: 38256kb)
Wrong Answer (Time: 40ms, Memory: 38320kb)
Wrong Answer (Time: 170ms, Memory: 38268kb)
Accepted (Time: 40ms, Memory: 38352kb)


Wrong Answer (Time: 110ms, Memory: 38260kb)
Wrong Answer (Time: 50ms, Memory: 38372kb)



我觉得应该是我的算法算上了内表面积,但想不到怎么解决,求帮助!
谢谢!

[解决办法]
从一个确定的体外点开始floodfill,再对floodfill以后的东西做统计。内部的洞是不会被floodfill算进去的

读书人网 >C++

热点推荐