luogu#P3693. 琪露诺的冰雪小屋
琪露诺的冰雪小屋
题目背景
琪露诺有一片正方形的雪地,她想在上面盖一栋小冰屋。
题目描述
琪露诺偶然间得到了一片 大小的正方形的雪地,她想在上面盖一栋冰雪小屋。
但调皮的⑨才不会认真地收集冰块呢,她要在这片土地上使用冰雪弹幕来制造冰砖,然后一块一块地搭起一个房子。
琪露诺制造冰砖的方式是这样的:她会站在某个方格上,然后向上,下,左,右,左上,左下,右上,右下这八个方向之一发射强力的冰雪弹幕,弹幕能影响到该方向一条直线上一定的距离以内的所有方格。
地面的每个方格都有一个冷冻度,初始为 。被冰雪弹幕影响一次,冷冻度 ,冷冻度的上限为 。
在发射弹幕的间隙中,琪露诺会来到所有冷冻度为 的格子,把那里的雪堆到一起,制作一个冰砖(大小为 方格),并且将冷冻度重新归零。
琪露诺会拿着这些冰砖来盖房子。这个房子的长度、宽度和坐落位置她在一开始就已经规划好了,但她并不愿意提早确定房子的高度。
琪露诺是这样计划的:这个房子外观上看起来是一个长方体。
她会先盖起这个房子的四面墙(厚度为 个方格),并在贴近地面的位置(废话)留一个宽度和高度分别为 和 的空位不放冰砖,作为房门。(显然,门无法开在墙的拐角处,但可以紧贴拐角)。
在她喜欢的时候,她会结束四面墙的建造,并一次性在墙顶部盖上一个厚度为 方格的屋顶,使房子成为一个空心有顶的长方体。
计划已经非常充分了,但琪露诺还是不放心,所以她想请你帮她写一个程序,来随时提醒着她别出什么差错。这个程序需要具备的功能将在下文详细介绍。
雪地由 行 列, 个方格组成。(下标从 开始,也就是说,存在第 行第 列,但不存在第 行第 列)每个方格都有一个冷冻度,范围 ,初始为 。注意,空间是三维的,而冷冻度只是地面的属性。
琪露诺想将房子的左上角放在第 行, 列(外墙也是房子的一部分,因此左上角位置不应该是房子的内部,而是外墙,并且是墙的拐角)。
这个房子的长度(平行于每列)是 ,宽度(平行于每行)是 ,包含墙。保证房子所占空间不会超出雪地的范围。
除了最后搭建屋顶,琪露诺只会在高度 放置冰砖。
一开始,琪露诺一个冰砖也没有。 在以下的介绍中,我们用俯视图来作示意:
0000
0000
4x90
0x01
数字代表当前该格子的冷冻度。如果位置紧贴地面(高度为 )的地方放上了冰砖,那么用字母 表示。
如果紧贴地面的位置没有冰砖,但是位置正上方的高空存在冰砖,那么仍然用数字表示地面的冷冻度,但这个数字会增加 。即如果在示意图中看到了一个数字 ,表示该位置地面是空的,但高处有冰砖,且地面的冷冻度为 。
第一个操作:ICE_BARRAGE R C D S
表示琪露诺站在第 行 列的位置,朝着方向 发射了一个强度为 的弹幕。
。
方向编号 表示上 , 表示左上 ,
表示左 , 表示左下 ,
表示下 , 表示右下 ,
表示右 , 表示右上 。
强度为 的弹幕,可以使“处在发射方向直线上,距离琪露诺不超过 格的所有格子(包括她站的格子)”的冷冻度都 。有以下几种特殊情况:
- 如果某个格子冷冻度为 ,那么该格子冷冻度不变。
- 如果弹幕所经路途上,有一个位置的地面上(高度为 )已经放了冰砖(就是弹幕撞上了琪露诺已经盖了一半的房子),那么弹幕将被阻挡,无法影响到冰砖所在的格子以及冰砖后面被挡住的格子。
- 弹幕超出雪地的部分忽略不计。
对于这个操作,需要如下输出一行:CIRNO FREEZED k BLOCK(S)
如果这个弹幕将某个方格的冷冻度成功增加了 ,那么认为这个弹幕冻住了该方格。
k
表示这个弹幕总共冻住了多少方格。
如图:发射弹幕前地图如下:
00000
00000
00000
000x0
00000
执行操作 ICE_BARRAGE 1 1 5 4
,地图变为:
00000
01000
00100
000x0
00000
输出:CIRNO FREEZED 2 BLOCK(S)
解释:琪露诺站在第一行第一列,面对右下角发射了一个强度为 的弹幕,但弹幕被 x
所阻挡,只能影响到 x
之前的格子。
第二个操作:MAKE_ICE_BLOCK
琪露诺走遍地图上所有冷冻度为 的方格,每个方格可以收集一个冰砖,然后将它们的冷冻度归零。
对于这个操作,你需要给出如下输出一行:CIRNO MADE x ICE BLOCK(S),NOW SHE HAS y ICE BLOCK(S)
表示琪露诺制造了 个冰砖,目前她有 个冰砖。
比如琪露诺一开始有 个冰砖,并且状态如下:
0xxx
0x4x
0x9x
0400
执行操作 MAKE_ICE_BLOCK
后变为
0xxx
0x0x
0x5x
0000
输出:CIRNO MADE 3 ICE BLOCK(S),NOW SHE HAS 3 ICE BLOCK(S)
在这个示例中,房子已经完成了一部分,x
表示墙,9
这个位置地面没有冰砖,但高处有(可以猜出是门)。房间内唯一一块空地、门的位置,以及房间外的一个位置的冷冻度都达到了 ,因此可以收集到 块冰砖,收集后将三个位置冷冻度都归零。
第三个操作:PUT_ICE_BLOCK R C H
表示在第 行,第 列,高度为 的地方放一个冰砖。。
贴近地面的位置高度为 。如果冰砖放置成功,那么琪露诺库存的冰砖数量将减 。
如果放置的位置贴近地面,该位置冷冻度立即归 。
有以下几种情况,序号越小优先级越高,并且只能满足一种情况。
如果满足 的话就忽视后面的,不满足 的前提下才可能满足 以此类推。
- 琪露诺目前没有任何冰砖,无法放置。这种情况下你需要输出:
CIRNO HAS NO ICE_BLOCK
- 冰砖将放在半空中,无法依附其他任何冰砖,或者目标位置已有冰砖了。
这种情况下你需要输出一行:BAKA CIRNO,CAN'T PUT HERE
,并无视此次操作,不做任何工作。 - 冰砖放在了规划建造房子的区域之外,即
或
或 或 。请输出一行:CIRNO MISSED THE PLACE
尽管琪露诺放错了地方,但你并不能阻止她放置这个冰砖。 - 冰砖留在了房子的内部,本应留空的地方被占用了,即
且
在屋顶的高度固定下来前,我们将所有满足上式的情况都认为是放在了房屋内部。
请输出一行:CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE
尽管琪露诺放错了地方,但你并不能阻止她放置这个冰砖。 - 冰砖放在了正确的位置(不必考虑是否堵住了留给门的地方)
请输出一行:CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS x ICE_BLOCK(S)
x
表示放过这块冰砖后琪露诺剩余的冰砖。
第四个操作:REMOVE_ICE_BLOCK R C H
表示取走第 行,第 列,高度为 处的冰砖。
有以下几种情况,序号越小优先级越高,并且只能满足一种情况。
如果满足 的话就忽视后面的,不满足 的前提下才可能满足 以此类推。
- 目标位置没有冰砖,输出一行:
BAKA CIRNO,THERE IS NO ICE_BLOCK
- 目标位置有冰砖,并且在这个冰砖被移走后,至少有一个冰砖形成了一个悬空的块。
如下面的“侧视图”,x
表示冰砖,0
表示空位。
xxxx
x000
x000
x000
在移走左上角的冰砖后,第一行右边三个冰砖没有了依靠,形成了一个悬空的连通块,就属于这种情况。
这个冰砖将成功移走,琪露诺的冰砖库存将会 。并且所有的悬空连通块都会掉下来摔碎并消失
(既不会进入冰砖库存,也不会在地面上留有任何痕迹)。
输出一行:CIRNO REMOVED AN ICE_BLOCK,AND k BLOCK(S) ARE BROKEN
,k
表示摔碎的冰砖数量。
3. 琪露诺挪走了冰砖,并且其他冰砖不受任何影响。
琪露诺的冰砖库存 ,输出一行:CIRNO REMOVED AN ICE_BLOCK
第五个操作:MAKE_ROOF
这个操作只会出现一次,并且只会作为最后一个操作。
这个操作表明琪露诺已经完成了冰雪小屋的四墙,只剩屋顶了!
一般情况下,琪露诺将放置最后的 个冰砖,把它们放置在墙壁最高的高度 的那一层,
形成一个屋顶。然后她移除所有多余的冰砖,接下来补好所有残缺的墙壁。
你需要按顺序来执行整个过程,一旦遇到某种用 标识的特殊情况,则执行完该情况后退出流程。
在特殊情况之间所描述的均为一般情况,只要之前没有因为满足某种特殊情况而退出流程,均认为满足了一般情况。
首先,琪露诺将会一次性放置最多 个冰砖来建造屋顶。
为什么是最多呢?请注意一点:如果之前错误放置在房子内部的冰砖恰好充当了屋顶的一部分,那么就不用在这个位置再放冰砖了。并且,所有比屋顶高的冰砖在之后将视为错误放置在了房子外部。
注意,放屋顶的时候可能会触及到高度为 的那个平面。
建造屋顶前后将会碰到两种特殊情况:
- 琪露诺剩余的冰砖不足以建造屋顶。输出一行:
SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF
- 墙壁的最高高度小于 个方格,或者内部有效空间小于两个方格。
墙壁所在的一圈不算内部空间。计算内部有效空间时请忽视错误放置的冰砖,因为它们将来要被移除。
输出一行:SORRY CIRNO,HOUSE IS TOO SMALL
(特殊情况结束)
此后,我们认为琪露诺已经造好了屋顶,接下来该移除所有多余冰砖了。在移除过程中,琪露诺会尽可能让更少的冰砖摔碎。如果墙壁上某个冰砖因为移走了多余的冰砖而将要摔碎,那么她会先拆掉墙壁上的那个冰砖,然后在填补墙壁残缺时重新补回来(显然,这种行为不会影响到墙壁有无残缺的定性,但可以少损失一个冰砖)。她不会故意拆掉一个处在墙壁上且不会摔碎的冰砖。
输出两行:
K1 ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED
K2 ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED
K1
表示房子内部错误放置的冰砖数量,K2
表示房子外部错误放置的冰砖数量。
将有可能遭遇一种特殊情况:
- 琪露诺移除了所有多余的冰砖,但在移除过程中,屋顶塌陷了。
输出一行:SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS
(特殊情况结束)
此后,我们认为琪露诺已经移除了所有多余的冰砖,接下来该填补墙壁的残缺了。
墙壁有残缺的定义是:除了宽为 ,高为 的门以外, 在房子内部看外面还能看到其他缺口。
如果某个空位将来要作为门的一部分,则不属于残缺。并且房子只能有一个门。
如果墙壁没有残缺,则不要填补,否则需要填补。你需要记下墙壁是否有残缺,之后会用到。
填补的策略是:使用尽可能少的冰砖,在正确的位置填补墙壁,使房屋的状态不满足墙壁有残缺的定义(即不能放置多余的冰砖,通过遮挡视线来达到目的)。在此定义下,大多数情况我们无需考虑四角的柱子是否完整,因为在房间里看不到。
将有可能遭遇一种特殊情况:
- 琪露诺剩余的冰砖不足以填补墙壁的残缺。
输出一行:SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL
(特殊情况结束)
此后,我们认为房子被成功建成了,这时你需要输出几行内容来对房子进行评价。
首先输出这么一行来庆祝房子的建成:GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE
- 在贴近地面的位置找不到一个宽度为 ,高度为 的位置留给门。
输出一行:HOUSE HAS NO DOOR
,然后琪露诺会尽可能利用墙壁上的残缺来开一个门。
否则,输出一行:DOOR IS OK
- 接下来输出一行表示填补之前墙壁的完整程度
2.1. 在之前的记录中,墙壁不完整而需要修补。输出:WALL NEED TO BE FIXED
2.2. 在之前的记录中,墙壁完整而无需修补。输出:WALL IS OK
- 接下来一行表示四角的完整程度。
如果四个角的柱子有不完整的地方,就输出:CORNER NEED TO BE FIXED
在这种情况下,如果琪露诺剩余的冰砖足够修复拐角的空缺,那么她直接会修复这个空缺。
如果不够的话,她会再多收集几个冰砖,数量恰好修复这个空缺,然后修复这个空缺。
否则,输出:CORNER IS OK
接下来,输出一行:CIRNO FINALLY HAS k ICE_BLOCK(S)
k
表示琪露诺最后剩余的冰砖的数量。
最后,如果在之前的记录中,墙壁完整无缺,没有一个位置需要填补。房子内外都无任何多余的方块,没有一个位置需要移除。没有出现房子没门的情况,房子四角的柱子也在造屋顶前完全造好,而不是通过修补完善的。并且门恰好开在了某面墙的正中央(如果长度为偶数,中间的两个都算),输出一行:
CIRNO IS PERFECT!
输入格式
第一行一个正整数 ,表示雪地的大小。
第二行一个正整数,表示琪露诺放置方块的最大高度。
第三行四个正整数 ,表示房子左上角位置的行列坐标,房子的长度以及宽度。
第四行一个正整数 ,表示操作的数量。
接下来 行,每行表示一个操作,输入格式见题目描述。
输出格式
在题目描述中已经介绍。
8
10
4 0 4 4
63
ICE_BARRAGE 2 1 1 3
ICE_BARRAGE 0 1 3 1
MAKE_ICE_BLOCK
PUT_ICE_BLOCK 3 2 0
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 2 0 6 7
ICE_BARRAGE 3 0 6 7
ICE_BARRAGE 4 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 4 0 0
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 3 0 1
REMOVE_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 4 2 0
PUT_ICE_BLOCK 6 1 0
PUT_ICE_BLOCK 4 3 0
PUT_ICE_BLOCK 5 3 0
PUT_ICE_BLOCK 6 3 0
PUT_ICE_BLOCK 7 3 0
ICE_BARRAGE 0 1 4 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
REMOVE_ICE_BLOCK 6 1 0
PUT_ICE_BLOCK 5 0 0
PUT_ICE_BLOCK 6 0 0
PUT_ICE_BLOCK 7 0 0
PUT_ICE_BLOCK 7 1 0
PUT_ICE_BLOCK 7 2 0
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 5 0 1
PUT_ICE_BLOCK 6 0 1
PUT_ICE_BLOCK 7 0 1
PUT_ICE_BLOCK 7 1 1
PUT_ICE_BLOCK 7 2 1
PUT_ICE_BLOCK 7 3 1
PUT_ICE_BLOCK 6 3 1
PUT_ICE_BLOCK 5 3 1
PUT_ICE_BLOCK 4 3 1
PUT_ICE_BLOCK 4 2 1
MAKE_ROOF
CIRNO FREEZED 2 BLOCK(S)
CIRNO FREEZED 2 BLOCK(S)
CIRNO MADE 0 ICE BLOCK(S),NOW SHE HAS 0 ICE BLOCK(S)
CIRNO HAS NO ICE_BLOCK
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO FREEZED 0 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 8 ICE BLOCK(S)
BAKA CIRNO,CAN'T PUT HERE
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 7 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 6 ICE_BLOCK(S)
CIRNO MISSED THE PLACE
CIRNO REMOVED AN ICE_BLOCK,AND 1 BLOCK(S) ARE BROKEN
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 5 ICE_BLOCK(S)
CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 3 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 2 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 1 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 0 ICE_BLOCK(S)
CIRNO FREEZED 6 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 8 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 16 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 24 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 32 ICE BLOCK(S)
CIRNO REMOVED AN ICE_BLOCK
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 32 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 31 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 30 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 29 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 28 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 27 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 26 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 25 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 24 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 23 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 22 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 21 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 20 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 19 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 18 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 17 ICE_BLOCK(S)
0 ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED
0 ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED
GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE
DOOR IS OK
WALL IS OK
CORNER IS OK
CIRNO FINALLY HAS 1 ICE_BLOCK(S)
CIRNO IS PERFECT!
提示
共分为 个 Subtask,每个 Subtask 的数据都满足一定条件,并且同时满足序号更大的 Subtask 的条件。
如 Subtask #0 同时满足 Subtask #0~5 的条件。
每一个 Subtask 的得分取所有测试点的最低分。
Subtask #0
琪露诺只想玩玩冰雪弹幕,她不会放置任何冰砖,也不会盖房子(即只有操作一和操作二)。
Subtask #1
琪露诺不会移除已经放置的冰砖。
Subtask #2
琪露诺很有信心,她将在没有 MAKE_ROOF
的情况下建造她的冰屋(这种情况下,放置方块的高度仍然会小于 且没有 MAKE_ROOF
操作)。
Subtask #3
琪露诺在移除方块时会谨慎考虑,不会造成任何冰砖摔落。MAKE_ROOF
操作移除多余冰砖时,也不会造成屋顶塌陷。
Subtask #4
琪露诺不喜欢把门开到四角的柱子旁边(数据保证在所有可能作为门的墙壁空缺中,有一种可能使得门不紧贴四角的柱子)。
Subtask #5
,,,保证不属于冰屋范围内的所有空地至多构成一个连通块。
注意:判断墙壁是否有残缺时,候选的开门位如果被方块堵住,在当时还未被清空。"能看到残缺"以当时的情况作为判断依据。