题解 P3693 【琪露诺的冰雪小屋】

· · 题解

嗯，一道看起来很恶心的模拟，实际上做起来大部分分还是很容易拿到的。

但貌似比赛的时候很少有人做，被题面长度吓住了吗？

第一个操作,放弹幕，很简单。

要注意如果琪露诺站在有冰砖的位置放弹幕，这个弹幕会直接被阻挡，等于无效。

第二个操作,收集冰砖，更简单。

直接遍历二维地图就可以了。

20分到手~

第三个操作，放冰砖。

注意一个细节，如果放到地面上，要把冷冻度归零。

30分到手，真容易

第四个操作，拿走冰砖。

不考虑摔碎的情况，非常好写，轻松50分到手

嗯,再来看看情况2...

什么？不是说好的模拟吗？怎么出来个找连通块？

好吧，这题不完全是模拟。

先删掉对应位置的方块，然后6遍BFS寻找连通块，注意如果某一块碰到了地面就不算悬空连通块。

大家内心:这么快就写完4/5了，这是什么辣鸡题，题面又长，难度又水。

出题人的内心是滑稽的

那么来看第五个操作,盖屋顶

*首先判断冰砖是否不足，直接遍历即可，有小细节。

*下来判断内部空间是否不足，第一种情况是屋顶太低，

第二种情况是四面墙挤到一起，没有内部空间。

*然后输出房屋内外有多少个冰砖，注意屋顶建成以后，高于屋顶的算作房屋外部，如果是之前放冰砖

时统计，这里就要跳坑了。

*接下来判断移除多余冰砖时屋顶会不会塌

和之前一样，BFS即可。

*接下来一个大坑来了，修复墙壁。

其他没问题，重点是四个角。

如果门没选在角落旁边，那么如果四个角有残缺，根本不用管它，因为看不到。

如果门选到角落旁边，缺角在房屋里面是有可能被看到的。

怎么解决呢？提供一个思路:查表。

我们用以下矩阵

a b

c d

来表示一堵墙角落的情况。假设a和c表示角方块，b和d表示相邻的边方块。0表示没有方块，1表示有方块。

那么对于

1 0

0 0

的情况，显然在房子内能看到c的缺损，所以要将c填上。

而对于

1 0

0 1

的情况，无需对c进行填补，因为d遮住了c使得c并不可见。

可以用方块摆一摆，比较直观。

#请注意一个开门位置有可能和两个角都相邻。

选择开门的位置时不妨采取估价的方法，以开门位置缺少的冰砖个数为第一关键字(越大价值越高)，修补角花费的冰砖数量为第二关键字(越小价值越高)，是否在正中间为第三关键字(是则价值更高)排序，选择价值最高的位置来开门即可。

*判断有没有门，上一个操作时应该顺便就弄了吧，没啥坑点。

*判断填补前墙壁是否完整，如果刚才修复墙壁的时候没注意到那个大坑，这里就会跳进去

*判断四角的完整程度，还是一样，修复墙壁的时候如果跳坑了，那么这里也跳坑了

*输出剩余冰砖数量，只要前面都写对了这里应该没问题。

*判断是否完美建造，同上。

好啦，这个题就结束了，已经有很多题解了，我自己代码写得太丑就不放了。

(std已经被hack掉好几次了，这次更新数据和题解也是发现了之前没注意到的特殊情况)

如果还发现一些非正确算法能通过此题，可以私戳我，我将会继续加强数据。非常感谢~