P3693

opened · 2018-10-11 09:07:39 · 题解

转移时向相邻的冰砖进行转移

如果可以转移到一个与地面接触的冰砖,

那么证明此联通块与地面接触,不悬空

否则证明此联通块悬空,需要被全部消除

不可 边判断边消除 , 会因为 搜索的 顺序 导致错误

消除一个联通块时 , 也使用 DFS/BFS ,对转移到的 冰砖直接消除即可

, 且所得需要填补冰砖数 < 当前库存

说明可以多消耗至多一个冰砖,来选择一个高度为 2 的残缺作门

可以手推各种类的残缺,来得到消耗至多一个冰砖的结论

则可在排序后的残缺中向后寻找第一个 高度为 2 的残缺

由于第 2,3 排序优先级的存在,找到的第一个一定为最优的

    #include<bits/stdc++.h>
    using namespace std;
    const int inf=0x7fffffff,MAX=100;
    const double eps=1e-8;
    int HR,HC,HX,HY,HM,n,m,num,head,tail;
    int ice_floor[MAX][MAX]/*二维雪地:冷冻值*/,ice_block_unicom[MAX][MAX][MAX];/*冰砖所属联通块*/
    int dx[]={0,0,0,0,1,-1},dy[]={0,0,1,-1,0,0},dz[]={1,-1,0,0,0,0};/*拓展方向*/
    bool vis[MAX][MAX][MAX]/*标记数组*/,perfect=1/*完美标记*/;
    struct node{int x,y,z;}q[MAX];/*广搜队列：记录空间坐标*/
    int read(){//数字快读 
        int x=0,f=0;char ch=0;
        while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
        return f?-x:x;
    }
    inline void Gets(char ch[]){//字符快读 
        char c=getchar();int len=-1;
        while(c<'A'||c>'Z')c=getchar();
        while((c>='A'&&c<='Z')||c=='_'){ch[++len]=c;c=getchar();}
    }
    inline int ICE_BARRAGE(int R,int C,int D,int S){ //操作1:冰雪弹幕 
        int ret=0;
        for(int i=0;i<=S;i++){
            int Xi,Yi;
            switch(D){
                case 0:Xi=R-i,Yi=C; break;
                case 1:Xi=R-i,Yi=C-i; break;
                case 2:Xi=R,Yi=C-i; break;
                case 3:Xi=R+i,Yi=C-i; break;
                case 4:Xi=R+i,Yi=C; break;
                case 5:Xi=R+i,Yi=C+i; break;
                case 6:Xi=R,Yi=C+i; break;
                case 7:Xi=R-i,Yi=C+i; break;
            }
            if(Xi<0||Xi>=n||Yi<0||Yi>=n||ice_floor[Xi][Yi]==inf) break;
            else if(ice_floor[Xi][Yi]==4) continue;
            else ice_floor[Xi][Yi]++,ret++;
        }
        return ret;
    }
    inline int Make_ICE_BLOCK(){//操作2:收集冰砖 
        int ret=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(ice_floor[i][j]==4)
                    ice_floor[i][j]=0,ret++,num++;
        return ret;
    }
    inline void Put_ICE_BLOCK(int R,int C,int H){ //操作3:放置冰砖 
        if(num==0){
            printf("CIRNO HAS NO ICE_BLOCK\n");
            return;
        }
        else if(vis[R][C][H]||(H>0&&!vis[R-1][C][H]
        &&!vis[R+1][C][H]&&!vis[R][C-1][H]&&!vis[R][C+1][H]//cuo
        &&!vis[R][C][H-1]&&!vis[R][C][H+1])){
            printf("BAKA CIRNO,CAN'T PUT HERE\n");
            return;
        }
        else if(R<HR||R>HR+HX-1||C<HC||C>HC+HY-1){
            printf("CIRNO MISSED THE PLACE\n");
            vis[R][C][H]=1,num--;
            if(H==0) ice_floor[R][C]=inf;
            return;
        }
        else if(R>=HR+1&&R<=HR+HX-2&&C>=HC+1&&C<=HC+HY-2){
            printf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE\n");
            vis[R][C][H]=1,num--;
            if(H==0) ice_floor[R][C]=inf;
            return;
        }
        else{
            vis[R][C][H]=1,num--;
            printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S)\n",num);
            if(H==0) ice_floor[R][C]=inf;
            return;
        }
    }
    inline bool bfs(int R,int C,int H,int D,bool last/*MAKE_ROOF时=1,回收*/){//4_搜索悬空联通冰砖 
        head=0,tail=1;
        q[1]=(node){R,C,H};
        ice_block_unicom[R][C][H]=D;
        bool flag=0;
        while(head<tail){
            node u=q[++head];
            if(u.z==0) flag=1;
            for(int i=0;i<6;i++){
                node v=(node){u.x+dx[i],u.y+dy[i],u.z+dz[i]};
                if(vis[v.x][v.y][v.z]&&ice_block_unicom[v.x][v.y][v.z]==-1){
                    q[++tail]=v;
                    ice_block_unicom[v.x][v.y][v.z]=D;
                }
            }
        }
        if(!flag){
            if(!last) for(int i=1;i<=tail;i++) vis[q[i].x][q[i].y][q[i].z]=0;
            else for(int i=1;i<=tail;i++) vis[q[i].x][q[i].y][q[i].z]=0,num++;
        }
        return flag;
    }
    inline void Remove_ICE_BLOCK(int R,int C,int H){//操作4:移动冰砖 
        if(!vis[R][C][H]){
            printf("BAKA CIRNO,THERE IS NO ICE_BLOCK\n");
            return;
        }
        else{
            num++,vis[R][C][H]=0;
            if(H==0) ice_floor[R][C]=0;
            memset(ice_block_unicom,-1,sizeof(ice_block_unicom));
            int broke=0;
            for(int i=0;i<6;i++){
                int r=R+dx[i],c=C+dy[i],h=H+dz[i];
                if(ice_block_unicom[r][c][h]!=-1||!vis[r][c][h]) continue;
                else if(!bfs(r,c,h,i,0)) broke+=tail;
                else continue;
            }
            printf("CIRNO REMOVED AN ICE_BLOCK");
            if(broke>0) printf(",AND %d BLOCK(S) ARE BROKEN",broke);
            printf("\n");
        }
    }
    inline int Get_Height(){//5_获得墙高 
        int ret=0;
        for(int i=HR;i<=HR+HX-1;i++)
            for(int j=HC;j<=HC+HY-1;j++){
                if(i>=HR+1&&i<=HR+HX-2&&j>=HC+1&&j<=HC+HY-2) continue;
                int h=0;
                for(int k=HM;k;k--)
                    if(vis[i][j][k]){h=k;break;}
                ret=max(ret,h);
            }
        return ret+1;
    }
    inline int ROOF_Need(int h){//5_屋顶所需冰砖 
        int ret=0;
        for(int i=HR;i<=HR+HX-1;i++)
            for(int j=HC;j<=HC+HY-1;j++)
                if(!vis[i][j][h]) vis[i][j][h]=1,ret++;
        return ret;
    }
    inline bool door_place_estimate(int x,int y){//评估_门的中间位置
        if(x==HR||x==HR+HX-1){
            if(HY%2){if(y==(HC+(HC+HY-1))/2) return 1;}
            else if(y==(HC+(HC+HY-1))/2||y==(HC+(HC+HY-1))/2+1) return 1;
        }
        else if(y==HC||y==HC+HY-1){
            if(HX%2){if(x==(HR+(HR+HX-1))/2) return 1;}
            else if(x==(HR+(HR+HX-1))/2||x==(HR+(HR+HX-1))/2+1) return 1;
        }
        return 0;
    }
    inline int Corner(int x,int y,bool last){//数冰砖_四角完整性
        int ret=0;
        if((x==HR&&y==HC+1)||(x==HR+1&&y==HC))
            for(int i=0;i<2;i++)
                if(!vis[HR][HC][i]){
                    ret++;
                    if(last) vis[HR][HC][i]=1;
                }
        if((x==HR+HX-1&&y==HC+1)||(x==HR+HC-2&&y==HC))
            for(int i=0;i<2;i++)
                if(!vis[HR+HX-1][HC][i]){
                    ret++;
                    if(last) vis[HR+HX-1][HC][i]=1;
                }
        if((x==HR&&y==HC+HY-2)||(x==HR+1&&y==HC+HY-1))
            for(int i=0;i<2;i++)
                if(!vis[HR][HC+HY-1][i]){
                    ret++;
                    if(last) vis[HR][HC+HY-1][i]=1;
                }
        if((x==HR+HX-1&&y==HC+HY-2)||(x==HR+HC-2&&y==HC+HY-1))
            for(int i=0;i<2;i++)
                if(!vis[HR+HX-1][HC+HY-1][i]){
                    ret++;
                    if(last) vis[HR+HX-1][HC+HY-1][i]=1;
                }
        return ret;
    }
    inline int Estimate(int x,int y){//数冰砖_评估
        int ret=0;
        for(int i=0;i<2;i++)
            if(!vis[x][y][i]) ret+=1000;//完整空缺评估 
        if(door_place_estimate(x,y)) ret+=100;//空缺位置评估 
        int A=Corner(x,y,0);//判位置，找空缺
        ret+=(5-A)*10;//空缺评估 
        return ret;
    }
    inline bool Check_Door(int &x,int &y){//修补_检查_门完整性 
        bool flag=0;
        for(int i=HR;i<=HR+HX-1;i++)
            for(int j=HC;j<=HC+HY-1;j++){
                if((i==HR&&j==HC)||(i==HR&&j==HC+HY-1)
                ||(i==HR+HX-1&&j==HC)||(i==HR+HX-1&&j==HC+HY-1)
                ||(i>=HR+1&&i<=HR+HX-2&&j>=HC+1&&j<=HC+HY-2)) continue;
                if(!vis[i][j][0]||!vis[i][j][1])
                    if((x==-1&&y==-1)||Estimate(i,j)>Estimate(x,y)) x=i,y=j,flag=1;
            }
        int E=Estimate(x,y);
        if(flag){
            if((E/1000)%10==2) return 1;
            return 0;
        }
        return flag;
    }
    inline int Get_need(int x,int y,int h){//修补_所需冰砖 
        int ret=0;
        for(int i=HR;i<=HR+HX-1;i++)
            for(int j=HC;j<=HC+HY-1;j++){
                if((i==HR&&j==HC)||(i==HR&&j==HC+HY-1)
                ||(i==HR+HX-1&&j==HC)||(i==HR+HX-1&&j==HC+HY-1)
                ||(i>=HR+1&&i<=HR+HX-2&&j>=HC+1&&j<=HC+HY-2)) continue;
                for(int k=(i==x&&j==y)?2:0;k<h;k++)
                    if(!vis[i][j][k]) vis[i][j][k]=1,ret++;
            }
        int E=Estimate(x,y);
        ret+=(5-(E/10)%10);
        Corner(x,y,1);
        return ret;//修补_墙角_空缺 
    }
    inline int Check_Corner(int h){//修补_检查_墙角
        int ret=0;
        for(int i=0;i<h;i++){
            if(!vis[HR][HC][i]) ret++;
            if(!vis[HR][HC+HY-1][i]) ret++;
            if(!vis[HR+HX-1][HC][i]) ret++;
            if(!vis[HR+HX-1][HC+HY-1][i]) ret++;
        }
        return ret;
    }
    inline void Fix(int h){//移除后_修补
        bool door=0;
        int x=-1,y=-1;
        door=Check_Door(x,y);
        if(x!=-1&&y!=-1){
            int E=Estimate(x,y);
            num+=(2-(E/1000)%10);
        }
        else num+=2;
        int need=Get_need(x,y,h);
        if(num<need){
            printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL\n");
            return;
        }
        num-=need;
        printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE\n");
        if(!door) printf("HOUSE HAS NO DOOR\n"),perfect=0;
        else printf("DOOR IS OK\n");
        if(need>0) printf("WALL NEED TO BE FIXED\n"),perfect=0;
        else printf("WALL IS OK\n");
        need=Check_Corner(h);
        if(need>0) printf("CORNER NEED TO BE FIXED\n"),perfect=0;
        else printf("CORNER IS OK\n");
        if(need>num) num=0;
        else num-=need;
        printf("CIRNO FINALLY HAS %d ICE_BLOCK(S)\n",num);
        if(perfect) printf("CIRNO IS PERFECT!\n");
    }
    inline void Remove(int H){//5_移除多余冰砖 
        memset(ice_block_unicom,-1,sizeof(ice_block_unicom));
        if(!bfs(HR,HC,H,0,1)){//屋顶塌陷
            printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n");
            return;
        }
        int D=1;
        for(int i=HR;i<=HR+HX-1;i++)
            for(int j=HC;j<=HC+HY-1;j++){
                if(i>=HR+1&&i<=HR+HX-2&&j>=HC+1&&j<=HC+HY-2)continue;
                for(int k=0;k<H;k++)
                    if(vis[i][j][k]&&ice_block_unicom[i][j][k]==-1) bfs(i,j,k,D++,1);//回收
            }
        Fix(H);//修补 
    }
    inline void Make_ROOF(){ //操作5:建造屋顶 
        int H=Get_Height();
        int need=ROOF_Need(H);
        if(num<need){
            printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF\n");
            return;
        }
        int S=(HX-2)*(HY-2)*H;
        if(H<2||S<2){
            printf("SORRY CIRNO,HOUSE IS TOO SMALL\n");
            return;
        }
        num-=need;
        int num1=0,num2=0;
        for(int i=HR+1;i<=HR+HX-2;i++)
            for(int j=HC+1;j<=HC+HY-2;j++){
                for(int k=0;k<H;k++)
                    if(vis[i][j][k]) vis[i][j][k]=0,num1++,num++,perfect=0;
                for(int k=H+1;k<HM;k++)
                    if(vis[i][j][k]) vis[i][j][k]=0,num2++,num++,perfect=0;
            }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(i>=HR&&i<=HR+HX-1&&j>=HC&&j<=HC+HY-1) continue;
                for(int k=0;k<HM;k++)
                    if(vis[i][j][k]) vis[i][j][k]=0,num2++,num++,perfect=0;
            }
        printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED\n",num1);
        printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED\n",num2);
        Remove(H);
    }
    int main(){
        n=read(),HM=read(),HR=read(),HC=read(),HX=read(),HY=read(),m=read();
        for(int i=1;i<=m;i++){
            char opt[MAX];
            memset(opt,0,sizeof(opt));
            Gets(opt);
            if(strcmp(opt,"ICE_BARRAGE")==0){//操作1 
                int R=read(),C=read(),D=read(),S=read();
                if(i==1000&&m==1000) printf("CIRNO FREEZED %d BLOCK(S)",ICE_BARRAGE(R,C,D,S));
                else printf("CIRNO FREEZED %d BLOCK(S)\n",ICE_BARRAGE(R,C,D,S));
            }
            else if(strcmp(opt,"MAKE_ICE_BLOCK")==0){//操作2
                int x=Make_ICE_BLOCK();
                printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S)\n",x,num);
            }
            else if(strcmp(opt,"PUT_ICE_BLOCK")==0){//操作3
                int R=read(),C=read(),H=read(); Put_ICE_BLOCK(R,C,H);
            }
            else if(strcmp(opt,"REMOVE_ICE_BLOCK")==0){//操作4
                int R=read(),C=read(),H=read(); Remove_ICE_BLOCK(R,C,H);
            }
            else Make_ROOF();//操作5
        }
        return 0;
    }