• UVA-12171 雕塑 题解答案代码 算法竞赛入门经典第二版

    GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

    这道题目在《算法竞赛入门经典第二版》书中标注了星号，也是第一道出现星号的题目。

    第一次遇到星号题，我还是有点害怕的。但是实际上没有那么难，就是有点麻烦而已。

    思路：

    题目本身比较好理解，实际上就是“三维图”的遍历，一个结点的周围节点是6个而已。

    由于中间的空心不计算，因此求体积和表面积时，只需要求外围的体积/面积即可。参考之前做过的UVA-1103  古代象形符号 题目，图片外围加一层边框，保证所有外围空白区域都是联通的。

    坐标理论上的最大值是500 * 500 * 500。直接用这么大的图遍历很可能超时，因此参考之前UVA-221 城市正视图 题目，对坐标进行去重和转换，遍历图使用新坐标，计算体积和面积时使用旧坐标。

    即使转换了坐标，图最大依旧可以达到100 * 100 * 100，使用dfs还是会爆栈，所以这里使用了bfs即可。（这个题目遍历顺序无所谓的）

    下面描述的是我的做法，不一定有普适性：

    至少要遍历图两次，第一次求哪些结点是外表面，第二次计算体积和表面积。

    对于一个方格，起点的格子是包含在方格内的，但是终点的结点对应的格子是不包含在方格内的，因此在构建图的时候，就要表明哪些结点属于方格的终点，这些点不包含在方格内。还要注意重叠点的情况，如果这个终点属于其他方格内部结点，那么就要被覆盖为内部结点。

    如果不标注，就会发生这种情况：

     2是方格的终点，2-3中间的区域应该是空的。但是在后续计算面积和体积时，因为2和3都有值，因此认为1-4是一片整个方格。中间的间隔没有被考虑到，因此计算错误。

    计算体积时，是用整个500 * 500 * 500的体积减去外围空白区域的体积来计算的，因此这时候需要在计算出的新坐标轴中加入0（最小点）和500（最大点），我实际取的值是505。

    计算面积时，由于是精确到每个区域来计算面积，因此会有两种模式：

    1. 本身为终点。

    这时候就要找该点上部3个面哪些点属于图形内部（本身为终点，不需要考虑下部），确定哪几个面属于终点的面。

    2. 本身为外部空白区域贴着的内部结点。这时候就要确定周围哪些结点是属于外部空白区域，以确认哪些是接触面。为了不重复计算，也只是计算上部3个面。因为如果是下部三个面存在接触面，则对应的下部的点就是终点，终点会去计算那些面。

    一定要确定是内外接触面，注意这个情况：

     里面的空白不要被认错成外部空白区域即可。

    AC代码

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. #define MAXN 505
    8. #define MAXM 105
    9.  
    10. const int stepX[6] = {1,-1,0,0,0,0}; 
    11. const int stepY[6] = {0,0,1,-1,0,0}; 
    12. const int stepZ[6] = {0,0,0,0,1,-1}; 
    13.  
    14. struct Box {
    15. 	int x0, y0, z0;
    16. 	int x, y, z; 
    17. };
    18.  
    19. struct Point {
    20. 	int x, y, z;
    21. }; 
    22.  
    23. Box arrBox[55];
    24. int boxlen;
    25.  
    26. int axisX[MAXM];
    27. int axisY[MAXM];
    28. int axisZ[MAXM];
    29. int lenx, leny, lenz;
    30.  
    31. int space[MAXM][MAXM][MAXM];
    32. bool findSpace[MAXM][MAXM][MAXM];
    33. int volume, area;
    34.  
    35. void clear() {
    36. 	memset(arrBox, 0, sizeof(arrBox));
    37. 	boxlen = 0;
    38. 	memset(axisX, 0, sizeof(axisX));
    39. 	memset(axisY, 0, sizeof(axisY));
    40. 	memset(axisZ, 0, sizeof(axisZ));
    41. 	lenx = 0;
    42. 	leny = 0;
    43. 	lenz = 0;
    44. 	memset(space, 0, sizeof(space));
    45. 	volume = 0;
    46. 	area= 0; 
    47. 	memset(findSpace, 0, sizeof(findSpace));
    48. }
    49.  
    50. void input() {
    51. 	int i;
    52. 	Box b;
    53. 	scanf("%d", &boxlen);
    54. 	for(i = 0; i < boxlen; ++i) {
    55. 		scanf("%d %d %d %d %d %d", &b.x0, &b.y0, &b.z0, &b.x, &b.y, &b.z);
    56. 		b.x += b.x0;
    57. 		b.y += b.y0;
    58. 		b.z += b.z0;
    59. 		arrBox[i] = b;
    60. 	}
    61. }
    62.  
    63. void handleAxis() {
    64. 	map<int, int> mpx, mpy, mpz;
    65. 	int i, j;
    66. 	for(i = 0; i < boxlen; ++i) {
    67. 		mpx[arrBox[i].x0] = 1;
    68. 		mpx[arrBox[i].x] = 1;
    69. 		mpy[arrBox[i].y0] = 1;
    70. 		mpy[arrBox[i].y] = 1;
    71. 		mpz[arrBox[i].z0] = 1;
    72. 		mpz[arrBox[i].z] = 1;
    73. 	}
    74. 	i = 1;
    75. 	for(auto ip = mpx.begin(); ip != mpx.end(); ++ip, ++i) {
    76. 		mpx[ip->first] = i;
    77. 		axisX[i] = ip->first;
    78. 	}
    79. 	lenx = i;
    80. 	axisX[lenx] = MAXN;
    81. 	axisX[lenx + 1] = MAXN;
    82. 	i = 1;
    83. 	for(auto ip = mpy.begin(); ip != mpy.end(); ++ip, ++i) {
    84. 		mpy[ip->first] = i;
    85. 		axisY[i] = ip->first;
    86. 	}
    87. 	leny = i;
    88. 	axisY[leny] = MAXN; 
    89. 	axisY[leny + 1] = MAXN;
    90. 	i = 1;
    91. 	for(auto ip = mpz.begin(); ip != mpz.end(); ++ip, ++i) {
    92. 		mpz[ip->first] = i;
    93. 		axisZ[i] = ip->first;
    94. 	}
    95. 	lenz = i;
    96. 	axisZ[lenz] = MAXN;
    97. 	axisZ[lenz + 1] = MAXN;
    98. 	for(i = 0; i < boxlen; ++i) {
    99. 		arrBox[i].x0 = mpx[arrBox[i].x0];
    100. 		arrBox[i].x = mpx[arrBox[i].x];
    101. 		arrBox[i].y0 = mpy[arrBox[i].y0];
    102. 		arrBox[i].y = mpy[arrBox[i].y];
    103. 		arrBox[i].z0 = mpz[arrBox[i].z0];
    104. 		arrBox[i].z = mpz[arrBox[i].z];
    105. 	}
    106. }
    107.  
    108. bool isEdge(int a) {
    109. 	return a / 1000 == 1;
    110. } 
    111.  
    112. void handleSpace() {
    113. 	int i, j, k, a;
    114. 	for(a = 0; a < boxlen; ++a) {
    115. 		for(i = arrBox[a].x0; i <= arrBox[a].x; ++i) {
    116. 			for(j = arrBox[a].y0; j <= arrBox[a].y; ++j) {
    117. 				for(k = arrBox[a].z0; k <= arrBox[a].z; ++k) {
    118. 					if(i == arrBox[a].x || j == arrBox[a].y || k == arrBox[a].z) {
    119. 						if(space[i][j][k] != 1) {
    120. 							space[i][j][k] = 1001;
    121. 							continue;
    122. 						}
    123. 					}
    124. 					space[i][j][k] = 1;
    125. 				}
    126. 			}
    127. 		}
    128. 	}
    129. }
    130.  
    131. void getBorder() {
    132. 	Point p;
    133. 	int i, a, b, c;
    134. 	queue qu;
    135. 	space[0][0][0] = 2;
    136. 	qu.push({0, 0, 0});
    137. 	while(!qu.empty()) {
    138. 		p = qu.front();
    139. 		qu.pop();
    140. 		for(i = 0; i < 6; ++i) {
    141. 			a = p.x + stepX[i];
    142. 			b = p.y + stepY[i];
    143. 			c = p.z + stepZ[i];
    144. 			if(a < 0 || a > lenx || b < 0 || b > leny || c < 0 || c > lenz) continue;
    145. 			if(space[a][b][c] % 1000 == 2) continue;
    146. 			if(space[a][b][c] == 0) space[a][b][c] = 2;
    147. 			if(isEdge(space[a][b][c])) space[a][b][c] = 1002;
    148. 			if(space[a][b][c] % 1000 == 2)
    149. 				qu.push({a, b, c}); 
    150. 		}
    151. 	}
    152. }
    153.  
    154. int getVolumeOne(int a, int b, int c) {
    155. 	return (axisX[a+1] - axisX[a]) * (axisY[b+1] - axisY[b]) * (axisZ[c+1] - axisZ[c]);
    156. }
    157.  
    158. int getAreaOne(int a, int b, int c) {
    159. 	int sum = 0;
    160. 	if(isEdge(space[a][b][c])) {
    161. 		if(space[a-1][b][c] == 1) {
    162. 			sum += (axisY[b+1] - axisY[b]) * (axisZ[c+1] - axisZ[c]);
    163. 		}
    164. 		if(space[a][b-1][c] == 1) {
    165. 			sum += (axisX[a+1] - axisX[a]) * (axisZ[c+1] - axisZ[c]);
    166. 		}
    167. 		if(space[a][b][c-1] == 1) {
    168. 			sum += (axisX[a+1] - axisX[a]) * (axisY[b+1] - axisY[b]);
    169. 		}
    170. 	}
    171. 	if(space[a][b][c] == 1) {
    172. 		if(space[a-1][b][c] % 1000 == 2) {
    173. 			sum += (axisY[b+1] - axisY[b]) * (axisZ[c+1] - axisZ[c]);
    174. 		}
    175. 		if(space[a][b-1][c] % 1000 == 2) {
    176. 			sum += (axisX[a+1] - axisX[a]) * (axisZ[c+1] - axisZ[c]);
    177. 		}
    178. 		if(space[a][b][c-1] % 1000 == 2) {
    179. 			sum += (axisX[a+1] - axisX[a]) * (axisY[b+1] - axisY[b]);
    180. 		}
    181. 	}
    182. 	return sum;
    183. }
    184.  
    185. void getVolumeAndArea() {
    186. 	volume = 0;
    187. 	area = 0;
    188. 	Point p;
    189. 	int i, a, b, c;
    190. 	queue qu;
    191. 	findSpace[0][0][0] = true;
    192. 	volume += getVolumeOne(0, 0, 0);
    193. 	qu.push({0, 0, 0});
    194. 	while(!qu.empty()) {
    195. 		p = qu.front();
    196. 		qu.pop();
    197. 		for(i = 0; i < 6; ++i) {
    198. 			a = p.x + stepX[i];
    199. 			b = p.y + stepY[i];
    200. 			c = p.z + stepZ[i];
    201. 			if(a < 0 || a >= lenx || b < 0 || b >= leny || c < 0 || c >= lenz) continue;
    202. 			if(findSpace[a][b][c]) continue;
    203. 			findSpace[a][b][c] = true;
    204. 			if(space[a][b][c] == 1 || space[a][b][c] == 1002) {
    205. 				area += getAreaOne(a, b, c);
    206. 			}
    207. 			if(space[a][b][c] % 1000 == 2) {
    208. 				volume += getVolumeOne(a, b, c);
    209. 				qu.push({a, b, c});
    210. 			}
    211. 		}
    212. 	}
    213. }
    214.  
    215. void outputValue() {
    216. 	int i, j ,k;
    217. 	for(i = 0; i <= lenx; ++i) {
    218. 		printf("%d ", axisX[i]);
    219. 	}
    220. 	putchar('\n');
    221. 	for(i = 0; i <= leny; ++i) {
    222. 		printf("%d ", axisY[i]);
    223. 	}
    224. 	putchar('\n');
    225. 	for(i = 0; i <= lenz; ++i) {
    226. 		printf("%d ", axisZ[i]);
    227. 	}
    228. 	putchar('\n');
    229. 	
    230. 	for(i = 0; i <= lenx; ++i) {
    231. 		for(j = 0; j <= leny; ++j) {
    232. 			for(k = 0; k <= lenz; ++k) {
    233. 				printf("%d %d %d %d\n", i, j, k, space[i][j][k]);
    234. 			}
    235. 		}
    236. 	}
    237. }
    238.  
    239. int main() {
    240. 	int T;
    241. 	scanf("%d", &T);
    242. 	while(T--) {
    243. 		clear();
    244. 		input();
    245. 		handleAxis();
    246. 		handleSpace(); 
    247. 		getBorder();
    248. 		getVolumeAndArea();
    249. 		volume = MAXN * MAXN * MAXN - volume;
    250. 		printf("%d %d\n", area, volume);
    251. 	}
    252. 	return 0;
    253. }

  • 相关阅读:
    Vector-valued function
    写了一款Jetbrains插件,为了Markdown
    【SpringBoot】SpringBoot怎么接收前端传递过来的数组
    2022春山东大学人工智能导论期末题库附答案
    ansible
    Python爬虫如何设置代理服务器（搭建代理服务器教程）
    PMP_强化练习题（一）180题（附答案及解析）
    CAPL学习之路-DoIP相关函数
    Java后端模拟面试，题集①
    python基于PHP+MySQL的校园帮忙领取快递平台
  • 原文地址：https://blog.csdn.net/qq278672818/article/details/126475749