UVa12171Sculpture雕塑

   题意大家去看,这里强调的是雕塑体积包括雕塑本身体积(这不是废话吗?)加上雕塑包含的空气的体积,表面积就是从外面看的面积,里面的面积不算。

  怎么解呢,相信大家已经知道了用floodfill与离散,对,这也是我要讲的方法,我会具体说一说怎么floodfill以及离散。

  对于这道题来说,离散是需要的,它能够将无穷或者极大转换成有限或者很小,这样能够达到省时间空间的目的。不过我们先不考虑离散,我们就先说floodfill,最后再考虑离散优化,解决题目还是要先考虑主要矛盾的,先从重点开始。

  什么是floodfill呢,就是我们将这个雕塑灌空气或水,不管灌什么,能将这个雕塑覆盖满即可,算体积直接从雕塑入手不是一个好办法,所以不妨试一试总的体积减去外围空气的体积,这样间接的方法能帮助我们进行计算里面的体积了对吧,可以形象的考虑这个问题相当于将一个不规则的物体浸入水中(空气中)。那么我们怎么算外围空气的体积呢,用dfs就行,dfs什么呢,我们从一个个小单位的块来考虑,要dfs就需要将它四周的遍历进去,一共有xyz三个轴6个方向,然后看看是不是空气还是物体就行,那么怎么表示物(空气雕塑)块呢,我们用一个点来表示,那就是这个物块xyz最小值来代表整个。

  下面说一说离散,为什么用离散,原因就是物块所在的空间位置太大了,500*500*500可不行啊,于是我们将大的位置与离散后的位置对应起来,所以在表示物块位置的时候用离散后的坐标来表示,在算体积与表面积时在对应后计算,尽量将离散前的大坐标位置不参与过多的计算,会耗费时空。

  可能讲的不是那么清楚,看一下代码就会理解了解很多,注意细节,代码我就不粘了,刘汝佳的代码值得学习!

原文地址:https://www.cnblogs.com/yifeiWa/p/10903083.html