琪露诺的冰雪小屋

原题链接 ： P3693

这是我至今在洛谷见过的细节最细的模拟题，也是我迄今施工时间最久的模拟题。

题面含义为模拟跟踪一个人从收集冰砖到建造冰屋的全过程，考虑了很多细节。

大致需要完成五个操作，难度呈递增排列且在最后直线上升（关于我在90分卡了20天这件事）

今天摸了一眼题解，想明白了一些实现，灵机一动对源程序进行了大修，侥幸通过了这道题。所以有感而发，写下这篇题解。

显然题干很长，但是本题对阅读理解的要求几乎不亚于语文的现代文阅读一。我们从前往后逐步分析各个操作 ：

第一个操作 ：ICE_BARRAGE R C D S

这是本题最好完成的操作，按照题意模拟即可，实现时可以专门开一个二维数组维护地面信息，用一个三维数组维护整个空间的冰块信息（反正后边肯定得开），注意地面的高度为$0$。
代码如下 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void ice_barrage(int x,int y,int fx,int s)
{//toward fx,the strength of the ice barrage.
    int ans = 0;
    int nx = x,ny = y;
    if(mp[nx][ny] < 4) mp[nx][ny]++,ans++;
    while(s--){
        nx = nx + dx[fx],ny = ny + dy[fx];
        if(block[nx][ny][0]) break;
        if(nx < 0 || ny < 0 || nx >= n || ny >= n) break;
        if(mp[nx][ny] < 4) mp[nx][ny] ++,ans++;
    }
    printf("CIRNO FREEZED %d BLOCK(S) \n",ans);
}

其中 fx 为冰雪弹幕的方向， s 为冰雪弹幕的强度（长度）

第二个操作：MAKE_ICE_BLOCK

依然很好写，遍历整片雪地即可，代码如下 ： 

1
2
3
4
5
6
7
8
inline void make_ice_block()
{
    int ans = 0;
    for(int i = 0;i<=n;i++)
    for(int j = 0;j<=n;j++) if(mp[i][j] == 4) mp[i][j] = 0,ans++;
    have_ice_block += ans;
    printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S) \n",ans,have_ice_block);
}

第三个操作：PUT_ICE_BLOCK R C H

放置冰砖，题目写到现在才开始有一点大模拟的样子。然而实际上细节仍然不多，按照题意描述简单判断即可。

放一下代码就是这样： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
inline void put_ice_block(int x,int y,int h)
{
    if(!have_ice_block){
        printf("CIRNO HAS NO ICE_BLOCK \n");
        return;
    }
    if(block[x][y][h]){
        printf("BAKA CIRNO,CAN'T PUT HERE \n");
        return;
    }
    if(!if_depended(x,y,h))
    {
        printf("BAKA CIRNO,CAN'T PUT HERE \n");
        return;
    }
    if(x < sta_x || x > end_x || y < sta_y || y > end_y)
    {
        printf("CIRNO MISSED THE PLACE \n");
        outside++;
        block[x][y][h] = 1;
        have_ice_block--;
        if(h == 0) mp[x][y] = 0;
        return;
    }
    if(x > sta_x && x < end_x && y > sta_y && y < end_y)
    {
        printf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE \n");
        // inside++;
        block[x][y][h] = 1;
        have_ice_block--;
        if(h == 0) mp[x][y] = 0;
        return;
    }
    block[x][y][h] = 1;
    have_ice_block--;
    if(h == 0) mp[x][y] = 0;
    printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S) \n",have_ice_block);
    return;
}

其中 block 数组是记录冰块（空间）状态的三维数组。if_depended 函数是用来判断当前位置是否与冰块相邻（即在此处放冰块有依靠，故名），其实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool if_depended(int x,int y,int h)
{
    if(h == 0) return true;
    for(int fx = 0;fx < 6;fx++)
    {
        int nx = x + sdx[fx];
        int ny = y + sdy[fx];
        int nh = h + sdh[fx];
        if(nx >= 0 && nx < n 
        && ny >= 0 && ny < n 
        && nh >= 0 && nh < maxh 
        && block[nx][ny][nh] ) return true;
    }
    return false;
}

数组 sdx,sdy,sdh 是三维空间下的方向数组，想必不用过多解释，这三个数组写起来是这样的：

1
2
3
int sdx[6] = {0,0,-1,1,0,0};
int sdy[6] = {0,0,0,0,1,-1};
int sdh[6] = {1,-1,0,0,0,0};

那么第三个操作就也完成了，下边是一个并不难的小难点：

第四个操作：REMOVE_ICE_BLOCK R C H

题目的细节到这里逐渐变多了起来。有无冰砖的判定可以由 block 数组直接得到。本操作唯一的难点在于判断冰块掉落摔碎的部分。我认为我在这一部分的处理并不是最简洁的，但是由测试表现来看至少应当是正确的。
我的思路是：先染色，记录每种颜色能到达的最低位置。对于最低高度为 $0$ 和被覆盖的颜色，无需操作；对于最低高度大于 $0$ 且不为初始极大值的颜色，删除相应颜色的所有冰块。
实现起来有一些细节，但是写了的话应该就不会错： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
inline void remove_ice_block(int x,int y,int h)
{
    if(!block[x][y][h])
    {
        printf("BAKA CIRNO,THERE IS NO ICE_BLOCK \n");
        return;
    }
    block[x][y][h] = 0;
    int bro = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 1;i<=6;i++) down[i] = maxh;
    for(int fx = 0;fx<6;fx++)
    {
        int nx = x + sdx[fx];
        int ny = y + sdy[fx];
        int nh = h + sdh[fx];
        depend_on_this(nx,ny,nh,fx+1);
        if(down[fx+1]) {
            bro += count(nx,ny,nh,fx+1);
        }
    }
    if(bro)
    {
        printf("CIRNO REMOVED AN ICE_BLOCK,AND %d BLOCK(S) ARE BROKEN \n",bro);
        have_ice_block++;
        return;
    }
    else{
        printf("CIRNO REMOVED AN ICE_BLOCK \n");
        have_ice_block++;
        return;
    }
    return;
}

其中函数 depend_on_this 是用来判断相应方向是否有冰块摔碎的函数，返回值为摔碎的冰块个数，用变量 bro 来记录，函数内部实现如下： 

1
2
3
4
5
6
7
8
9
10
11
inline void depend_on_this(int x,int y,int h,int t)
{
    if(x < 0 || x >= n || y < 0 || y >= n || h < 0 || h > maxh) return ;
    if(!block[x][y][h]) return;
    if(vis[x][y][h]) return;
    vis[x][y][h] = t;
    down[t] = min(down[t],h);
    if(down[t] == 0) return;
    for(int fx = 0;fx<6;fx++)
        depend_on_this(x+sdx[fx],y+sdy[fx],h+sdh[fx],t);
}

其中数组 vis 就是上文染色的颜色记录，数组 down 下标为颜色编号，记录了每种颜色对应的最小高度。
count 函数是统计并删除相应颜色的函数，实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
inline int count(int x,int y,int h,int t)
{
    if(x < 0 || x >= n || y < 0 || y >= n || h < 0 || h > maxh) return 0;
    if(!block[x][y][h]) return 0;
    if(vis[x][y][h] != t) return 0;
	if(x < sta_x || x > end_x || y < sta_y || y > end_y) outside--;
    block[x][y][h] = 0;
    int ans = 1;
    for(int fx = 0;fx<6;fx++)
    ans += count(x + sdx[fx],y + sdy[fx],h + sdh[fx],t);
    return ans;
}

其中的含义应当是显然的（。那么前四个操作就都完成了。这道题到这里最多是一道绿题罢大概，接下来才是难度直线上升的部分 ：

第五个操作：MAKE_ROOF

全题尾杀（

这个操作代表了从封屋顶到修整房屋的全过程。大部分内容依然可以只靠模拟完成，只放 make_roof 函数的话大概长这样 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
inline void make_roof()
{
	wall_h = 0;
	for(int x = sta_x,y = sta_y;y <= end_y;y++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int x = end_x,y = sta_y;y <= end_y;y++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int y = sta_y,x = sta_x;x <= end_x;x++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int y = end_y,x = sta_x;x <= end_x;x++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    int roof_h = wall_h + 1;
    int need_blocks = 0;
    for(int i = sta_x;i<=end_x;i++)
    for(int j = sta_y;j<=end_y;j++)
    {
        if(!block[i][j][roof_h]) 
        need_blocks++,block[i][j][roof_h] = 1;
    }

    if(have_ice_block < need_blocks)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF \n");
        exit(0);
    }
    have_ice_block -= need_blocks;
    if(roof_h < 2){
        printf("SORRY CIRNO,HOUSE IS TOO SMALL \n");
        exit(0);
    }
    int house_room = (len_x - 2) * (len_y - 2) * (roof_h - 1);
    if(house_room < 2){
        printf("SORRY CIRNO,HOUSE IS TOO SMALL \n");
        exit(0);
    }
    inside = 0;
	outside = 0;
	for(int x = 0;x<n;x++)
	for(int y = 0;y<n;y++)
	for(int h = 0;h<maxh;h++)
	{
		if(!block[x][y][h]) continue;
		if(x < sta_x || x > end_x || y < sta_y || y > end_y || h > roof_h)
		{
			outside++;
			continue;
		}
		if(x > sta_x && x < end_x && y > sta_y && y < end_y && h < roof_h)
		{
			inside++;
			continue;
		}
	}
	have_ice_block += inside;
    have_ice_block += outside;
    printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED \n",inside);
    printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED \n",outside);
    memset(vis,0,sizeof(vis));
    down[1] = roof_h;
    if_collapse(sta_x,sta_y,roof_h);
    if(down[1] != 0){
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS \n");
        exit(0);
    }
    need_blocks = 0;
    int la_corner_need = 0;
    for(int x = sta_x,y = sta_y + 1;y < end_y;y++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int x = end_x,y = sta_y + 1;y < end_y;y++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int y = sta_y,x = sta_x + 1;x < end_x;x++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int y = end_y,x = sta_x + 1;x < end_x;x++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    
    bool pd = if_door();
    need_blocks -= door.cnt();
    if(door.exist && by_the_corner(door))
    {
    	la_corner_need += need_fill_corner(door);
        if(la_corner_need)
        fix_the_corner(door);
    }
    need_blocks += la_corner_need;
    if(need_blocks > have_ice_block){
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL \n");
        exit(0);
    }
    printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE \n");
    have_ice_block -= need_blocks;
    if(pd){
        printf("DOOR IS OK \n");
    }
    else {
        printf("HOUSE HAS NO DOOR \n");
    }
    have_ice_block += 2 - door.cnt();
    if(need_blocks){
        printf("WALL NEED TO BE FIXED \n");
    }
    else {
        printf("WALL IS OK \n");
    }
    int corner_need = 0;
    for(int h = 0;h<=wall_h;h++)
    {
        if(!block[sta_x][sta_y][h]) corner_need++;
        if(!block[end_x][sta_y][h]) corner_need++;
        if(!block[sta_x][end_y][h]) corner_need++;
        if(!block[end_x][end_y][h]) corner_need++;
    }
    if(corner_need){
        printf("CORNER NEED TO BE FIXED \n");
        if(have_ice_block >= corner_need) have_ice_block -= corner_need;
        else have_ice_block = 0;
    }
    else{
        printf("CORNER IS OK \n");
    }
    printf("CIRNO FINALLY HAS %d ICE_BLOCK(S) \n",have_ice_block);
    if(!need_blocks && !corner_need && !inside && !outside 
    && door.exist && door.cnt() == 2 && in_the_middle(door) )
    {
        printf("CIRNO IS PERFECT! ");
    }
    return;
}

因为封住屋顶会影响冰块在屋内和屋外的定性，且整个空间并不大，所以可以考虑遍历整个空间来更新屋内冰块和屋外冰块（inside,outside）的值。这样易写不易错。

去掉多余方块后可能会导致屋顶坍塌——当多余方块撑起了房顶的重量时。判断是否坍塌的过程与上文取走冰块后的判断类似，像是这样 ：

1
2
3
4
5
6
7
8
9
10
11
inline void if_collapse(int x,int y,int h)
{
    if((x != sta_x && x != end_x) || (y != sta_y && y != end_y)) return ;
    if(vis[x][y][h]) return;
    if(!block[x][y][h]) return;
    if(down[1] == 0) return;
    vis[x][y][h] = 1;
    down[1] = min(down[1],h);
    for(int fx = 0;fx<6;fx++)
        if_collapse(x+sdx[fx],y+sdy[fx],h+sdh[fx]);
}

（以上是染色函数）

本题最有 E 趣 X 的部分就是它关于门的一系列判断。首先我们可以开一个结构体来存储一个门的信息，这将为后续操作带来极大的便利，就像这样 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct DOOR{
    bool exist;
    int x;
    int y;
    int cnt() {return (block[x][y][0] == 0) + (block[x][y][1] == 0);}
    friend bool operator < (DOOR a,DOOR b)
    {
        if(a.cnt() != b.cnt()) return a.cnt() < b.cnt();
        int dis_a = max( min(a.x - sta_x, end_x - a.x) , min(a.y - sta_y,end_y - a.y) );
        int dis_b = max( min(b.x - sta_x, end_x - b.x) , min(b.y - sta_y,end_y - b.y) );
        if(dis_a == dis_b && dis_a == 1)
        {
            return need_fill_corner(a) > need_fill_corner(b);
        }
        return dis_a < dis_b;
    }
    friend bool operator > (DOOR a,DOOR b)
    {
        return b < a;
    }
}door;

其中cnt表示以在这个坐标（二维）处开门需要移除的冰块数量，由题目可知这应当是判断门优先级的第一关键字。其次是在这个坐标处开门是否会使柱子的残缺对判断墙壁残缺时造成影响——若将门开到墙角处，那么判断墙壁是否残缺时能看到的柱子部分的完整程度将被算入墙壁当中，这是第二关键字。第三关键字是门是否开在中间，这有关于最后对perfect的判断。

所以更新门的过程也可以写成一个函数 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void add_door(int x,int y)
{
    if(!door.exist)
    {
        door.exist = 1;
        door.x = x;
        door.y = y;
        return;
    }
    DOOR nxt_door = (DOOR){1,x,y};
    door = max(door,nxt_door);
    return;
}

可见其中一个重要的函数是 need_fill_corner 这个函数的实现如下 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int need_fill_corner(DOOR x)
{
    if(!by_the_corner(x)) return 0;
    int ans = 0;
	if(x.x == sta_x)
    {
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) ans ++;
   		}
    	if(x.y == end_y - 1)
        {
   			if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
    }
   	if(x.x == end_x)
	{
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[end_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][sta_y][1]) ans ++;
            
    	}
   		if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) ans ++;
   		}
   	}
    if(x.y == sta_y)
    {
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) ans ++;
   		}
    	if(x.x == end_x - 1)
        {
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
    }
   	if(x.y == end_y)
	{
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
   		if(x.x == end_x - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) ans ++;
   		}
   	}
    return ans;
}

其返回值为传入的 door 对应位置需要在判断墙壁是否残缺时需要填补的柱子方块数。

判断一扇门是否挨着柱子是非常容易的 ：

1
2
3
4
5
6
7
8
inline bool by_the_corner(DOOR x)
{
	if(x.x == sta_x || x.x == end_x)
		return ( x.y - sta_y == 1 || end_y - x.y == 1);
    if(x.y == sta_y || x.y == end_y) 
        return ( x.x - sta_x == 1 || end_x - x.x == 1);
    return false;
}

判断一扇门是否开在某墙壁的最中央也一样简单 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
inline bool in_the_middle(DOOR x)
{
	if(x.x == sta_x || x.x == end_x)
	{
		if(len_y & 1)
		{
			return (x.y == sta_y + len_y / 2);
		}
		else
		{
			return (x.y == sta_y + len_y / 2 || x.y == sta_y + len_y / 2 - 1);
		}
	}
	else
	{
		if(len_x & 1)
		{
			return (x.x == sta_x + len_x / 2);
		}
		else
		{
			return (x.x == sta_x + len_x / 2 || x.x == sta_x + len_x / 2 - 1);
		}
	}
}

此时我们显然不能修补柱子，但是当判断完墙壁是否残缺后我们应当对柱子进行修补，代码十分相似 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
inline void fix_the_corner(DOOR x)
{
    if(!by_the_corner(x)) return ;
    int ans = 0;
	if(x.x == sta_x)
    {
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) block[sta_x][sta_y][0] = 1;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) block[sta_x][sta_y][1] = 1;
   		}
    	if(x.y == end_y - 1)
        {
   			if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[sta_x][end_y][0] = 1;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[sta_x][end_y][1] = 1;
    	}
    }
   	if(x.x == end_x)
	{
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[end_x][sta_y][0]) block[end_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][sta_y][1]) block[end_x][sta_y][1] = 1; 
    	}
   		if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) block[end_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) block[end_x][end_y][1] = 1; 
   		}
   	}
    if(x.y == sta_y)
    {
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) block[sta_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) block[sta_x][sta_y][1] = 1; 
   		}
    	if(x.x == end_x - 1)
        {
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[end_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[end_x][sta_y][1] = 1; 
    	}
    }
   	if(x.y == end_y)
	{
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[sta_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[sta_x][end_y][1] = 1;
    	}
        if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) block[end_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) block[end_x][end_y][1] = 1;
   		}
   	}
    return ;
}

再强调一下最容易踩的坑 ：

  • 判断墙壁是否有残缺时，仅当门紧挨柱子时需要检查柱子是否完整，并且只需要检查门的缺口同一高度的相邻柱子，注意一扇门可以同时紧邻两个柱子

写到这里这道题就基本结束了，最后再放一下本题代码（其实几乎就是上边的各个片段拼接起来） ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define RE return 0
// #define file
#define N 20
#define H 22
#define M 1010

int inside;
int outside;
int mp[N][N];
int down[10];
int sta_x,sta_y;
int len_x,len_y;
int end_x,end_y;
int vis[N][N][N];
int have_ice_block;
bool block[N][N][N];
int n,m,maxh,wall_h;
int sdx[6] = {0,0,-1,1,0,0};
int sdy[6] = {0,0,0,0,1,-1};
int sdh[6] = {1,-1,0,0,0,0};
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,-1,-1,-1,0,1,1,1};

struct DOOR;
void work();
void input();
bool if_door();
void make_roof();
void make_ice_block();
void add_door(int ,int );
bool in_the_middle(DOOR );
bool by_the_corner(DOOR );
int need_fill_corner(DOOR );
void fix_the_corner(DOOR );
int count(int ,int ,int ,int );
void if_collapse(int ,int ,int );
bool if_depended(int ,int ,int );
void put_ice_block(int ,int ,int );
void ice_barrage(int ,int ,int ,int );
void remove_ice_block(int ,int ,int );
void depend_on_this(int ,int ,int ,int );

struct DOOR{
    bool exist;
    int x;
    int y;
    int cnt() {return (block[x][y][0] == 0) + (block[x][y][1] == 0);}
    friend bool operator < (DOOR a,DOOR b)
    {
        if(a.cnt() != b.cnt()) return a.cnt() < b.cnt();
        int dis_a = max( min(a.x - sta_x, end_x - a.x) , min(a.y - sta_y,end_y - a.y) );
        int dis_b = max( min(b.x - sta_x, end_x - b.x) , min(b.y - sta_y,end_y - b.y) );
        if(dis_a == dis_b && dis_a == 1)
        {
            return need_fill_corner(a) > need_fill_corner(b);
        }
        return dis_a < dis_b;
    }
    friend bool operator > (DOOR a,DOOR b)
    {
        return b < a;
    }
}door;



int main()
{
#ifdef file
    freopen("print.txt","w",stdout);
#endif
    input();
    work();
    RE;
}

inline void input()
{
    scanf("%d",&n);
    scanf("%d",&maxh);
    scanf("%d%d%d%d",&sta_x,&sta_y,&len_x,&len_y);
    end_x = sta_x + len_x - 1;
    end_y = sta_y + len_y - 1;
    scanf("%d",&m);
}

inline void work()
{
    string opt;
    int a,b,c,d;
    for(int i = 1;i<=m;i++)
    {
        cin >> opt;
        if(opt == "ICE_BARRAGE")
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            ice_barrage(a,b,c,d);
        }
        else if(opt == "MAKE_ICE_BLOCK")
        {
            make_ice_block();
        }
        else if(opt == "PUT_ICE_BLOCK")
        {
            scanf("%d%d%d",&a,&b,&c);
            put_ice_block(a,b,c);
        }
        else if(opt == "REMOVE_ICE_BLOCK")
        {
            scanf("%d%d%d",&a,&b,&c);
            remove_ice_block(a,b,c);
        }
        else
        {
            make_roof();
        }
    }
}

inline void ice_barrage(int x,int y,int fx,int s)
{//toward fx,the strength of the ice barrage.
    int ans = 0;
    int nx = x,ny = y;
    if(mp[nx][ny] < 4) mp[nx][ny] ++,ans++;
    while(s--){
        nx = nx + dx[fx],ny = ny + dy[fx];
        if(block[nx][ny][0]) break;
        if(nx < 0 || ny < 0 || nx >= n || ny >= n) break;
        if(mp[nx][ny] < 4) mp[nx][ny] ++,ans++;
    }
    printf("CIRNO FREEZED %d BLOCK(S) \n",ans);
}

inline void make_ice_block()
{
    int ans = 0;
    for(int i = 0;i<=n;i++)
    for(int j = 0;j<=n;j++) if(mp[i][j] == 4) mp[i][j] = 0,ans++;
    have_ice_block += ans;
    printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S) \n",ans,have_ice_block);
}

bool if_depended(int x,int y,int h)
{
    if(h == 0) return true;
    for(int fx = 0;fx < 6;fx++)
    {
        int nx = x + sdx[fx];
        int ny = y + sdy[fx];
        int nh = h + sdh[fx];
        if(nx >= 0 && nx < n 
        && ny >= 0 && ny < n 
        && nh >= 0 && nh < maxh 
        && block[nx][ny][nh] ) return true;
    }
    return false;
}

inline void put_ice_block(int x,int y,int h)
{
    if(!have_ice_block){
        printf("CIRNO HAS NO ICE_BLOCK \n");
        return;
    }
    if(block[x][y][h]){
        printf("BAKA CIRNO,CAN'T PUT HERE \n");
        return;
    }
    if(!if_depended(x,y,h))
    {
        printf("BAKA CIRNO,CAN'T PUT HERE \n");
        return;
    }
    if(x < sta_x || x > end_x || y < sta_y || y > end_y)
    {
        printf("CIRNO MISSED THE PLACE \n");
        outside++;
        block[x][y][h] = 1;
        have_ice_block--;
        if(h == 0) mp[x][y] = 0;
        return;
    }
    if(x > sta_x && x < end_x && y > sta_y && y < end_y)
    {
        printf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE \n");
        block[x][y][h] = 1;
        have_ice_block--;
        if(h == 0) mp[x][y] = 0;
        return;
    }
    block[x][y][h] = 1;
    have_ice_block--;
    if(h == 0) mp[x][y] = 0;
    printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S) \n",have_ice_block);
    return;
}

inline void remove_ice_block(int x,int y,int h)
{
    if(!block[x][y][h])
    {
        printf("BAKA CIRNO,THERE IS NO ICE_BLOCK \n");
        return;
    }
    block[x][y][h] = 0;
    int bro = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 1;i<=6;i++) down[i] = maxh;
    for(int fx = 0;fx<6;fx++)
    {
        int nx = x + sdx[fx];
        int ny = y + sdy[fx];
        int nh = h + sdh[fx];
        depend_on_this(nx,ny,nh,fx+1);
        if(down[fx+1]) {
            bro += count(nx,ny,nh,fx+1);
        }
    }
    if(bro)
    {
        printf("CIRNO REMOVED AN ICE_BLOCK,AND %d BLOCK(S) ARE BROKEN \n",bro);
        have_ice_block++;
        return;
    }
    else{
        printf("CIRNO REMOVED AN ICE_BLOCK \n");
        have_ice_block++;
        return;
    }
    return;
}

inline void depend_on_this(int x,int y,int h,int t)
{
    if(x < 0 || x >= n || y < 0 || y >= n || h < 0 || h > maxh) return ;
    if(!block[x][y][h]) return;
    if(vis[x][y][h]) return;
    vis[x][y][h] = t;
    down[t] = min(down[t],h);
    if(down[t] == 0) return;
    for(int fx = 0;fx<6;fx++)
        depend_on_this(x+sdx[fx],y+sdy[fx],h+sdh[fx],t);
}

inline int count(int x,int y,int h,int t)
{
    if(x < 0 || x >= n || y < 0 || y >= n || h < 0 || h > maxh) return 0;
    if(!block[x][y][h]) return 0;
    if(vis[x][y][h] != t) return 0;
	if(x < sta_x || x > end_x || y < sta_y || y > end_y) outside--;
    block[x][y][h] = 0;
    int ans = 1;
    for(int fx = 0;fx<6;fx++)
    ans += count(x + sdx[fx],y + sdy[fx],h + sdh[fx],t);
    return ans;
}

inline void make_roof()
{
	wall_h = 0;
	for(int x = sta_x,y = sta_y;y <= end_y;y++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int x = end_x,y = sta_y;y <= end_y;y++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int y = sta_y,x = sta_x;x <= end_x;x++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    for(int y = end_y,x = sta_x;x <= end_x;x++)
    for(int h = wall_h;h<maxh;h++)
        if(block[x][y][h]) wall_h = h;
    int roof_h = wall_h + 1;
    int need_blocks = 0;
    for(int i = sta_x;i<=end_x;i++)
    for(int j = sta_y;j<=end_y;j++)
    {
        if(!block[i][j][roof_h]) 
        need_blocks++,block[i][j][roof_h] = 1;
    }

    if(have_ice_block < need_blocks)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF \n");
        exit(0);
    }
    have_ice_block -= need_blocks;
    if(roof_h < 2){
        printf("SORRY CIRNO,HOUSE IS TOO SMALL \n");
        exit(0);
    }
    int house_room = (len_x - 2) * (len_y - 2) * (roof_h - 1);
    if(house_room < 2){
        printf("SORRY CIRNO,HOUSE IS TOO SMALL \n");
        exit(0);
    }
    inside = 0;
	outside = 0;
	for(int x = 0;x<n;x++)
	for(int y = 0;y<n;y++)
	for(int h = 0;h<maxh;h++)
	{
		if(!block[x][y][h]) continue;
		if(x < sta_x || x > end_x || y < sta_y || y > end_y || h > roof_h)
		{
			outside++;
			continue;
		}
		if(x > sta_x && x < end_x && y > sta_y && y < end_y && h < roof_h)
		{
			inside++;
			continue;
		}
	}
	have_ice_block += inside;
    have_ice_block += outside;
    printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED \n",inside);
    printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED \n",outside);
    memset(vis,0,sizeof(vis));
    down[1] = roof_h;
    if_collapse(sta_x,sta_y,roof_h);
    if(down[1] != 0){
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS \n");
        exit(0);
    }
    need_blocks = 0;
    int la_corner_need = 0;
    for(int x = sta_x,y = sta_y + 1;y < end_y;y++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int x = end_x,y = sta_y + 1;y < end_y;y++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int y = sta_y,x = sta_x + 1;x < end_x;x++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    for(int y = end_y,x = sta_x + 1;x < end_x;x++)
    for(int h = 0;h<=wall_h;h++)
        if(!block[x][y][h]) need_blocks++;
    
    bool pd = if_door();
    need_blocks -= door.cnt();
    if(door.exist && by_the_corner(door))
    {
    	la_corner_need += need_fill_corner(door);
        if(la_corner_need)
        fix_the_corner(door);
    }
    need_blocks += la_corner_need;
    if(need_blocks > have_ice_block){
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL \n");
        exit(0);
    }
    printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE \n");
    have_ice_block -= need_blocks;
    if(pd){
        printf("DOOR IS OK \n");
    }
    else {
        printf("HOUSE HAS NO DOOR \n");
    }
    have_ice_block += 2 - door.cnt();
    if(need_blocks){
        printf("WALL NEED TO BE FIXED \n");
    }
    else {
        printf("WALL IS OK \n");
    }
    int corner_need = 0;
    for(int h = 0;h<=wall_h;h++)
    {
        if(!block[sta_x][sta_y][h]) corner_need++;
        if(!block[end_x][sta_y][h]) corner_need++;
        if(!block[sta_x][end_y][h]) corner_need++;
        if(!block[end_x][end_y][h]) corner_need++;
    }
    if(corner_need){
        printf("CORNER NEED TO BE FIXED \n");
        if(have_ice_block >= corner_need) have_ice_block -= corner_need;
        else have_ice_block = 0;
    }
    else{
        printf("CORNER IS OK \n");
    }
    printf("CIRNO FINALLY HAS %d ICE_BLOCK(S) \n",have_ice_block);
    if(!need_blocks && !corner_need && !inside && !outside 
    && door.exist && door.cnt() == 2 && in_the_middle(door) )
    {
        printf("CIRNO IS PERFECT! ");
    }
    return;
}

int need_fill_corner(DOOR x)
{
    if(!by_the_corner(x)) return 0;
    int ans = 0;
	if(x.x == sta_x)
    {
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) ans ++;
   		}
    	if(x.y == end_y - 1)
        {
   			if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
    }
   	if(x.x == end_x)
	{
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[end_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][sta_y][1]) ans ++;
            
    	}
   		if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) ans ++;
   		}
   	}
    if(x.y == sta_y)
    {
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) ans ++;
   		}
    	if(x.x == end_x - 1)
        {
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
    }
   	if(x.y == end_y)
	{
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) ans ++;
    	}
   		if(x.x == end_x - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) ans ++;
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) ans ++;
   		}
   	}
    return ans;
}

inline void fix_the_corner(DOOR x)
{
    if(!by_the_corner(x)) return ;
    int ans = 0;
	if(x.x == sta_x)
    {
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) block[sta_x][sta_y][0] = 1;
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) block[sta_x][sta_y][1] = 1;
   		}
    	if(x.y == end_y - 1)
        {
   			if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[sta_x][end_y][0] = 1;
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[sta_x][end_y][1] = 1;
    	}
    }
   	if(x.x == end_x)
	{
    	if(x.y == sta_y + 1)
    	{
   			if(!block[x.x][x.y][0] && !block[end_x][sta_y][0]) block[end_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][sta_y][1]) block[end_x][sta_y][1] = 1; 
    	}
   		if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) block[end_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) block[end_x][end_y][1] = 1; 
   		}
   	}
    if(x.y == sta_y)
    {
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][sta_y][0]) block[sta_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][sta_y][1]) block[sta_x][sta_y][1] = 1; 
   		}
    	if(x.x == end_x - 1)
        {
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[end_x][sta_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[end_x][sta_y][1] = 1; 
    	}
    }
   	if(x.y == end_y)
	{
    	if(x.x == sta_x + 1)
    	{
            if(!block[x.x][x.y][0] && !block[sta_x][end_y][0]) block[sta_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[sta_x][end_y][1]) block[sta_x][end_y][1] = 1;
    	}
        if(x.y == end_y - 1)
		{
            if(!block[x.x][x.y][0] && !block[end_x][end_y][0]) block[end_x][end_y][0] = 1; 
            if(!block[x.x][x.y][1] && !block[end_x][end_y][1]) block[end_x][end_y][1] = 1;
   		}
   	}
    return ;
}

inline bool by_the_corner(DOOR x)
{
	if(x.x == sta_x || x.x == end_x)
		return ( x.y - sta_y == 1 || end_y - x.y == 1);
    if(x.y == sta_y || x.y == end_y) 
        return ( x.x - sta_x == 1 || end_x - x.x == 1);
    return false;
}

inline bool in_the_middle(DOOR x)
{
	if(x.x == sta_x || x.x == end_x)
	{
		if(len_y & 1)
		{
			return (x.y == sta_y + len_y / 2);
		}
		else
		{
			return (x.y == sta_y + len_y / 2 || x.y == sta_y + len_y / 2 - 1);
		}
	}
	else
	{
		if(len_x & 1)
		{
			return (x.x == sta_x + len_x / 2);
		}
		else
		{
			return (x.x == sta_x + len_x / 2 || x.x == sta_x + len_x / 2 - 1);
		}
	}
}

inline void if_collapse(int x,int y,int h)
{
    if((x != sta_x && x != end_x) || (y != sta_y && y != end_y)) return ;
    if(vis[x][y][h]) return;
    if(!block[x][y][h]) return;
    if(down[1] == 0) return;
    vis[x][y][h] = 1;
    down[1] = min(down[1],h);
    for(int fx = 0;fx<6;fx++)
        if_collapse(x+sdx[fx],y+sdy[fx],h+sdh[fx]);
}

inline bool if_door()
{
    for(int x = sta_x,y = sta_y + 1;y < end_y;y++)
        if(!block[x][y][0] || !block[x][y][1]) add_door(x,y);
    for(int x = end_x,y = sta_y + 1;y < end_y;y++)
        if(!block[x][y][0] || !block[x][y][1]) add_door(x,y);
    for(int y = sta_y,x = sta_x + 1;x < end_x;x++)
        if(!block[x][y][0] || !block[x][y][1]) add_door(x,y);
    for(int y = end_y,x = sta_x + 1;x < end_x;x++)
        if(!block[x][y][0] || !block[x][y][1]) add_door(x,y);
    return door.exist && door.cnt() == 2;
}

inline void add_door(int x,int y)
{
    if(!door.exist)
    {
        door.exist = 1;
        door.x = x;
        door.y = y;
        return;
    }
    DOOR nxt_door = (DOOR){1,x,y};
    door = max(door,nxt_door);
    return;
}

}

int main()
{
    return Pozhu :: main();
}

/*
log : 
    2022.6.22 : Start the program.
    2022.6.28 : Continued the program,fixed leaving problems.
                Passed the subtask #0 , 20 pts.
                Passed the subtask #1 , 30 pts.
                Passed the subtask #2 , 50 pts.
    2022.6.29 : Finished some functions.
    2022.6.30 : Passed the subtask #3 , 70 pts.
                Our class were broken . I'm sad.
    2022.7.3  : Fixed the bug in count ans depended_on_this.
    2022.7.9  : Finished the functions.
                Passed the suctask #4  , 90 pts.
    2022.7.29 ：Changed some parts about the door.
                Found a big problem,fixed.
                100 pts.
                
*/

结语：

从写完这道题至今也有一周多的时间了，回头想想当时debug的过程真的很不容易。缝缝补补写完了这篇题解（今天也是因为身体不适写不动别的东西才来补完这个最好补的坑），所以大概题解的质量并不很好——就当是我自己对于这道小有名气的模拟题的回顾罢。

by Pozhu
2022.8.9