题解:琪露诺的冰雪小屋luogu3693

庆祝通过noip2018初赛,系列五题EP1.

题目描述:

https://www.luogu.org/problemnew/show/P3693

调试记录:  真的很爽

下面是代码:

目前写过的最长的代码

  1#include<bits/stdc++.h>
2#define N 21 
3#define map ___map
4using namespace std;
5int n,m,cnt_block,R,C,D,S,HR,HC,HX,HY,HM,H,not_outside,maxhigh,ret1,ret2;
6int map[N][N][N],is_ice[N][N][N],temp[N][N];
7bool skip,vis[N][N][N],bo,un,last,wall,unt;
8const int dic[8][2]={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
9const int dir[6][3]={{1,0,0},{0,1,0},{0,0,1},{-1,0,0},{0,-1,0},{0,0,-1}};
10string ch;
11struct node{int x,y,z;};
12bool inside(int x,int y,int z){
13    if (x<0||x>=n||y<0||y>=n||z<0||z>HM) 
14        return false;
15    return true;
16}
17int remove_fall(int xxx,int yyy,int zzz){
18    if (map[xxx][yyy][zzz]==0return 0;
19    memset(vis,false,sizeof(vis)); 
20    queue<node> Q;
21    Q.push({xxx,yyy,zzz}); vis[xxx][yyy][zzz]=true;
22    bo=falseint res=0;
23    while (!Q.empty()){
24        node ver=Q.front(); Q.pop();
25        if (ver.z==0){ bo=true;break;}
26        for (int i=0;i<6;i++){
27            int xx=ver.x+dir[i][0],yy=ver.y+dir[i][1],zz=ver.z+dir[i][2];
28            if (inside(xx,yy,zz))
29                if (!vis[xx][yy][zz] && map[xx][yy][zz]==2){
30                    vis[xx][yy][zz]=true;
31                    Q.push({xx,yy,zz});
32                }
33        }
34    } 
35    if (!bo)
36        for (int i=0;i<n;i++)
37            for (int j=0;j<n;j++)
38                for (int k=0;k<HM;k++)
39                    if (vis[i][j][k]) res++,map[i][j][k]=0;
40    return res;
41}
42void read(){
43    cin >> n;
44    cin >> HM;
45    cin >> HR >> HC >> HX >> HY;
46    cin >> m;
47    memset(temp,0,sizeof(temp));
48    memset(map,0,sizeof(map)); 
49
50int solve_ICE_BARRAGE(int R,int C,int D,int S){
51    int r=R,c=C;
52    int res=0;
53    for (int i=0;i<=S;i++){
54        if (map[r][c][0]==2||r<0||c<0||r>=n||c>=n) return res;
55        if (temp[r][c]<4)
56            res++,temp[r][c]++;
57        r+=dic[D][0]; c+=dic[D][1];
58    }
59    return res;
60}
61int solve_MAKE_ICE_BLOCK(){
62    int res=0;
63    for (int i=0;i<n;i++)
64        for (int j=0;j<n;j++)
65            if (temp[i][j]>=4){
66                res++; temp[i][j]-=4;
67                cnt_block++;
68            }
69    return res;
70}
71int solve_PUT_ICE_BLOCK(int R,int C,int H){
72    if (cnt_block==0){
73        skip=falseprintf("CIRNO HAS NO ICE_BLOCK ");
74        return 0;
75    }
76    if (H!=0)
77        if (map[R+1][C][H]!=2&&map[R-1][C][H]!=2&&map[R][C+1][H]!=2&&map[R][C-1][H]!=2&&map[R][C][H+1]!=2&&map[R][C][H-1]!=2){
78            skip=false;printf("BAKA CIRNO,CAN'T PUT HERE ");
79            return 0;
80        }
81    if (map[R][C][H]==2){
82        skip=false;printf("BAKA CIRNO,CAN'T PUT HERE ");
83        return 0;
84    }
85    map[R][C][H]=2;
86    cnt_block--;
87    if (H==0) temp[R][C]=0;
88    if (R<HR||R>HR+HX-1||C<HC||C>HC+HY-1){
89        skip=falseprintf("CIRNO MISSED THE PLACE ");
90        return 0;
91    }
92    if (R>=HR+1&&R<=HR+HX-2&&C>=HC+1&&C<=HC+HY-2){
93        skip=falseprintf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE ");
94        return 0;
95    }
96    return cnt_block;
97}
98
99int solve_REMOVE_ICE_BLOCK(int R,int C,int H){
100    if (map[R][C][H]!=2){
101        skip=falseprintf("BAKA CIRNO,THERE IS NO ICE_BLOCK ");
102        return -1;
103    }
104    map[R][C][H]=0; cnt_block++;
105    int rs=0;
106    for (int i=0;i<6;i++)
107        if (inside(R+dir[i][0],C+dir[i][1],H+dir[i][2]))
108            rs+=remove_fall(R+dir[i][0],C+dir[i][1],H+dir[i][2]);
109    return rs;
110}
111void solve_MAKE_ROOF(){
112    int res=0,size=0;;
113    maxhigh=0;
114    for (int i=HR;i<HX+HR;i++)
115        for (int j=HC;j<HY+HC;j++)
116            for (int k=0;k<HM;k++){
117                if(map[i][j][k]==2 && (i==HX+HR-1||j==HY+HC-1||i==HR||j==HC))
118                    maxhigh=max(maxhigh,k);
119            }
120    maxhigh++;
121
122    for (int i=HR;i<HX+HR;i++)
123        for (int j=HC;j<HY+HC;j++)
124            if (map[i][j][maxhigh]!=2) res++,map[i][j][maxhigh]=2;
125    if (res>cnt_block){
126        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF ");
127        un=false;
128        return;
129    }
130    cnt_block-=res;
131    size=(HX-2)*(HY-2)*(maxhigh-1);
132    if (size<=2 || maxhigh <2){
133        un=false;
134        printf("SORRY CIRNO,HOUSE IS TOO SMALL ");
135        return;
136    }
137}
138int count_inside(){
139    not_outside=0int res=0;
140    for (int i=HR;i<HX+HR;i++)
141        for (int j=HC;j<HY+HC;j++)
142            for (int k=0;k<maxhigh;k++){
143                if (map[i][j][k]==2&&i!=HX+HR-1&&j!=HY+HC-1&&i!=HR&&j!=HC) res++;
144                if (map[i][j][k]==2) not_outside++;
145                if (k==maxhigh-2 && (i==HX+HR-1||j==HY+HC-1||i==HR||j==HC)&&map[i][j][k]==2) skip=false;
146            }
147    cnt_block+=res;
148    return res;
149}
150int count_outside(){
151    int res=0;
152    for (int i=0;i<n;i++)
153        for (int j=0;j<n;j++)
154            for (int k=0;k<HM;k++){
155                if (map[i][j][k]==2) res++;
156                if (k==maxhigh&&i<HX+HR&&j<HY+HC&&i>=HR&&j>=HC&&map[i][j][k]==2)
157                    res--;
158            }
159    res-=not_outside;
160    cnt_block+=res;
161    return res;
162}
163void build_roof(){
164    for (int i=HR;i<HX+HR;i++)
165        for (int j=HC;j<HY+HC;j++)
166            map[i][j][maxhigh]=2;
167}
168bool just_fix(int X,int Y){
169    int res=cnt_block;
170    for (int i=HR+1;i<=HR+HX-2;i++)
171        for (int j=0;j<=maxhigh;j++){
172            if (map[i][HC][j]!=2 && (i!=X||j>1||Y!=HC)){
173                cnt_block--; 
174                map[i][HC][j]=2;
175            }
176            if (map[i][HC+HY-1][j]!=2 && (i!=X||j>1||Y!=HC+HY-1)){
177                cnt_block--;
178                map[i][HC+HY-1][j]=2;
179            }    
180        }
181    for (int i=HC+1;i<=HC+HY-2;i++){
182        for (int j=0;j<=maxhigh;j++){
183            if (map[HR][i][j]!=2 && (HR!=X||j>1||Y!=i)){
184                cnt_block--;
185                map[HR][i][j]=2;
186            }
187            if (map[HR+HX-1][i][j]!=2 && (HR+HX-1!=X||j>1||Y!=i)){
188                cnt_block--;
189                map[HR+HX-1][i][j]=2;
190            }    
191        }
192    }
193    if (cnt_block<0){
194        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL ");
195        unt=false;
196    }
197    if (res!=cnt_block){
198        wall=false;
199        return false;
200    } 
201    return true;
202}
203bool do_sth(int X,int Y){
204    int res=cnt_block;
205    for (int i=0;i<2;i++){
206        if (map[HR][HC][i]!=2&&((X==HR&&Y==HC+1)||(X==HR+1&&Y==HC))){
207            cnt_block--;
208            map[HR][HC][i]=2;
209        }
210        if (map[HR][HC+HY-1][i]!=2&&((X==HR&&Y==HC+HY-2)||(X==HR+1&&Y==HC+HY-1))){
211            cnt_block--;
212            map[HR][HC+HY-1][i]=2;
213        }
214        if (map[HR+HX-1][HC][i]!=2&&((X==HR+HX-2&&Y==HC)||(X==HR+HX-1&&Y==HC+1))){
215            cnt_block--;
216            map[HR+HX-1][HC][i]=2;
217        }
218        if (map[HR+HX-1][HC+HY-1][i]!=2&&((X==HR+HX-1&&Y==HC+HY-2)||(X==HR+HY-2&&Y==HC+HY-1))){
219            cnt_block--;
220            map[HR+HX-1][HC+HY-1][i]=2;
221        }
222    }
223    if (res!=cnt_block){
224        wall=false;
225        return false;
226    }
227    return true;
228}
229bool fix_wall(){
230    bool flag=true,flag1=trueint X=-1,Y=-1; bo=false;wall=true;
231    for (int i=HR+1;i<HR+HX-1;i++){
232        if (map[i][HC][0]!=2) X=i,Y=HC; 
233        if (map[i][HC+HY-1][0]!=2) X=i,Y=HC+HY-1;
234    }
235    for (int i=HC+1;i<HC+HY-1;i++){
236        if (map[HR][i][0]!=2) X=HR,Y=i;
237        if (map[HR+HX-1][i][0]!=2) X=HR+HX-1,Y=i;
238    }
239    if (X!=-1 && map[X][Y][1]==2)
240        cnt_block++;
241    flag=just_fix(X,Y); 
242    flag=do_sth(X,Y);
243    if (unt){
244        printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE ");
245        if (X==-1||Y==-1||map[X][Y][1]==2)
246            printf("HOUSE HAS NO DOOR "),last=falseelse
247            printf("DOOR IS OK ");
248    }
249    if (X==-1)
250        cnt_block+=2
251    return flag;
252}
253bool fix_corner(){
254    int res=0;
255    for (int i=0;i<=maxhigh;i++){
256        if (map[HR][HC][i]!=2) res++;
257        if (map[HR][HC+HY-1][i]!=2) res++;
258        if (map[HR+HX-1][HC][i]!=2) res++;
259        if (map[HR+HX-1][HC+HY-1][i]!=2) res++; 
260    }
261    if (res==0)
262        return trueelse{
263            cnt_block-=res;
264            cnt_block=max(0,cnt_block);
265            return false;
266        }
267}
268void solve(){
269    un=true;
270    for (int i=1;i<=m;i++){
271        cin>>ch;
272        if (ch=="ICE_BARRAGE"){
273            scanf("%d%d%d%d",&R,&C,&D,&S);
274            int ret=solve_ICE_BARRAGE(R,C,D,S);
275            if (i!=m)  
276                printf("CIRNO FREEZED %d BLOCK(S) ",ret); else
277                printf("CIRNO FREEZED %d BLOCK(S)",ret);
278        }
279        if (ch=="MAKE_ICE_BLOCK"){
280            int ret=solve_MAKE_ICE_BLOCK();
281            printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S) ",ret,cnt_block);
282        }
283        if (ch=="PUT_ICE_BLOCK"){
284            scanf("%d%d%d",&R,&C,&H);
285            skip=true;
286            int ret=solve_PUT_ICE_BLOCK(R,C,H);
287            if (skip)
288                printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S) ",ret);
289        }
290        if (ch=="REMOVE_ICE_BLOCK"){
291            scanf("%d%d%d",&R,&C,&H);
292            skip=true;
293            int ret=solve_REMOVE_ICE_BLOCK(R,C,H);
294            if (skip)
295                if (ret<1)
296                    printf("CIRNO REMOVED AN ICE_BLOCK "); else 
297                    printf("CIRNO REMOVED AN ICE_BLOCK,AND %d BLOCK(S) ARE BROKEN ",ret);
298        }
299        if (ch=="MAKE_ROOF"){
300            solve_MAKE_ROOF();
301            if (!un) break;
302            last=skip=true;
303            ret1=count_inside();
304            ret2=count_outside();
305            printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED ",ret1);
306            printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED ",ret2);
307            if (skip){printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS "); break;}
308            unt=true;
309            fix_wall();
310            if (!unt) break
311            if (wall)
312                printf("WALL IS OK "); else
313                printf("WALL NEED TO BE FIXED "),last=false;
314            if (fix_corner())
315                printf("CORNER IS OK "); else
316                printf("CORNER NEED TO BE FIXED "),last=false
317            printf("CIRNO FINALLY HAS %d ICE_BLOCK(S) ",cnt_block);
318            if (last && ret1==0 && ret2==0 )
319                printf("CIRNO IS PERFECT! ");
320        }
321    }    
322
323int main(){
324//    freopen("xiaowu18.in","r",stdin);
325//    freopen("xiaowu.out","w",stdout);
326    read();
327    solve();
328    return 0;
329
原文地址:https://www.cnblogs.com/titititing/p/9822517.html