P3693 琪露诺的冰雪小屋题解

DimensionTripper · 2018-07-24 20:33:56 · 题解

超级大模拟，简直写的我头疼，但终于还是A掉了，所以来写一篇题解QwQ

首先，我们不管别的，拿20分再说，然后我们发现20分其实挺好拿的啊，瞎jb搞一搞分就来了。以下是20分核心代码：

int num;//这是⑨现在有的冰砖数量
int frz[MAXN][MAXN];//frz数组记录地面的冷冻值,如果有冰砖则为inf
il int Spell_Card(int x,int y,int dir,int s)//弹幕操作，暴力搞就完了
{
    int ret=0;
    for(ri i=0;i<=s;i++)
    {
        int Xi,Yi;
        switch(dir)
        {
            case 0:Xi=x-i,Yi=y;break;
            case 1:Xi=x-i,Yi=y-i;break;
            case 2:Xi=x,Yi=y-i;break;
            case 3:Xi=x+i,Yi=y-i;break;
            case 4:Xi=x+i,Yi=y;break;
            case 5:Xi=x+i,Yi=y+i;break;
            case 6:Xi=x,Yi=y+i;break;
            case 7:Xi=x-i,Yi=y+i;break;
        }
        if(Xi<0||Xi>=n||Yi<0||Yi>=n||frz[Xi][Yi]==inf)
            break;
        else if(frz[Xi][Yi]==4)
            continue;
        else
        {
            frz[Xi][Yi]++;
            ret++;
        }
    }
    return ret;
}
il int Make()//做冰砖，直接n*n枚举每一块地面就行了
{
    int ret=0;
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
            if(frz[i][j]==4)
                frz[i][j]=0,ret++,num++;
    return ret;
}

20分之后，我们会发现30分其实也挺好写的，于是瞎搞一下就又多了10分。以下是30分核心（其实就是PUT_ICE_BLOCK的操作了）

il void Put(int r,int c,int h)
{
    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]&&!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)
            frz[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)
            frz[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)
            frz[r][c]=inf;
        return;
    }
}

别看我打得长，其实没多大的思维难度，毕竟出题人很仁慈地把位置位于屋内屋外的判定条件都给出来了，直接抄就行了。

要注意的有两点：

“可依靠的方块”为上下左右前后六个方向，对没错，上面也可以。
一定要判定h=0，即冰砖放在地上的情况，要将frz[x][y]修改为inf。然后就没太大问题了。

30分之后，我们遇到了第一个难题：如何判断悬空联通块。

实际上，如果BFS学的比较熟练的几乎不需要思考，在移除方块之后向6个方向做BFS就完了，如果搜到了h=0的方块，就可以保留，如果搜完了还没有遇到h=0的方块，那么这就是一个悬空联通块了，这个时候所有进过队的方块都要删掉，删掉并统计一下就行了。

以下是50分的核心：

int f[MAXN][MAXN][MAXN];//每个方块所属的联通块
int dx[]={0,0,0,0,1,-1};
int dy[]={0,0,1,-1,0,0};
int dz[]={1,-1,0,0,0,0};
bool vis[MAXN][MAXN][MAXN];
struct node
{
    int x,y,z;
};
node q[MAXN];
il bool BFS(int r,int c,int h,int dir)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri 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]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
        for(ri i=1;i<=fr;i++)
            vis[q[i].x][q[i].y][q[i].z]=0;//对悬空联通块的处理
    return flag;
}
il void Remove(int r,int c,int h)
{
    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)
            frz[r][c]=0;
        memset(f,-1,sizeof(f));
        int brk=0;
        for(ri i=0;i<6;i++)
        {
            int R=r+dx[i],C=c+dy[i],H=h+dz[i];
            if(f[R][C][H]!=-1||!vis[R][C][H])//对6个方向做BFS
                continue;
            else if(!BFS(R,C,H,i))
                brk+=fr;
            else
                continue;
        }
        printf("CIRNO REMOVED AN ICE_BLOCK");
        if(brk>0)
            printf(",AND %d BLOCK(S) ARE BROKEN",brk);
        printf("\n");
    }
}

写到这里也许你们会说：这也不是特别难啊，题面又长，还特别水，结果4/5不是一下就打完了吗？然而出题人表示这才刚刚开始呢。

先来看70分，建造屋顶时没有塌陷与方块掉落，也就是说不用BFS，可是我们注意到之前的BFS改造一下就可以放过来用，于是就可以直接冲90分了。

以下是90分部分核心：

il bool BFS(int r,int c,int h,int dir,bool last)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri 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]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
    {
        if(!last)
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0;
        else
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0,num++;
    }
    return flag;
}

修改之后的BFS，增加一个last标记，判定是否为MAKE_ROOF时进行的。是，则由于题目条件给出，对悬空联通块中的冰砖进行回收。

bool perfect=1;
il int Get_Height()
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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(ri k=Hm;k;k--)
                if(vis[i][j][k])
                {
                    h=k;
                    break;
                }
            ret=max(ret,h);
        }
    return ret+1;
}//房屋高度
il int Get_Need(int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
            if(!vis[i][j][h])
                vis[i][j][h]=1,ret++;
    return ret;
}
il bool Check_place(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;
}//判断一个坐标是否在某面墙的正中间
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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)||(!Check_place(x,y)&&Check_place(i,j)))
                    x=i,y=j,flag=1;
            }
        }
    return flag;
}//判断是否有完整的门
il void Get_door_place(int &x,int &y)
{
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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)||(!Check_place(x,y)&&Check_place(i,j)))
                    x=i,y=j;
            }
        }
}//寻找门的位置
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    return ret;
}//墙上的空缺也是暴力枚举
il int Check_Corner(int h)
{
    int ret=0;
    for(ri 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;
}//枚举四个角落寻找空缺
il void Fix(int h)
{
    bool door=0,corner=0;
    int x=-1,y=-1;
    door=Check_Door(x,y);//检查是否有完整的门
    if(!door)
        Get_door_place(x,y);//没有完整的门就寻找只需要拆掉一块冰砖的位置
    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");
}
il void Remove_Blocks(int h)
{
    memset(f,-1,sizeof(f));
    if(!BFS(Hr,Hc,h,0,1))
    {
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n");
        return;
    }//优先判断屋顶塌陷的情况
    int dir=1;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            for(ri k=0;k<h;k++)
                if(vis[i][j][k]&&f[i][j][k]==-1)
                    BFS(i,j,k,dir++,1);
        }//回收墙上的悬空联通块
    Fix(h);//修复
}
il void Make_Roof()
{
    int h=Get_Height();//获取屋顶高度
    int need=Get_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;//num1-->屋内|num2-->屋外
    for(ri i=Hr+1;i<=Hr+Hx-2;i++)
        for(ri j=Hc+1;j<=Hc+Hy-2;j++)
        {
            for(ri k=0;k<h;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num1++,num++,perfect=0;
            for(ri k=h+1;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;//注意,这里是一个大坑。
        }//回收屋内冰砖
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
        {
            if(i>=Hr&&i<=Hr+Hx-1&&j>=Hc&&j<=Hc+Hy-1)
                continue;
            for(ri 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_Blocks(h);
}

这样大概就有90-95分了，要注意的是封上屋顶后，高于h的冰砖也算是屋外冰砖了。

然后我们会发现第二组数据非常的奇怪，墙壁上没有空缺标准输出却有WALL NEED TO BE FIXED，而本有空缺的角落却输出了CORNER IS OK。怎么回事呢？数据有问题吗？不是，如果再回去仔细读题会发现题目对墙壁有残缺的定义是“在屋内能看到缺口”，而#2的情况中，门被开在了角落旁边，这样角落的空缺就能被看见了。

那么怎么办？只判定门的位置是否在中间的方法肯定不行了，单独打特判的话绝对会疯掉，毕竟我不想再像出题人那样为10分多打200行。于是我想到了对每个可能作为门的位置进行估价，选取估价较高的位置作为门。

以下是核心部分：

il bool Mid(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;
}//这就是之前的Check_door_placeQwQ
il int Corner(int x,int y,bool last)
{
    int ret=0;
    if((x==Hr&&y==Hc+1)||(x==Hr+1&&y==Hc))
    {
        for(ri 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(ri 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(ri 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(ri 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;
}//也是暴力，懒的解释了QwQ
il int Evaluate(int x,int y)
{
    int ret=0;
    for(ri i=0;i<2;i++)
        if(!vis[x][y][i])
            ret+=1000;//由于我们优先选择更完整的空隙作为门，所以完整度的估价最高
    if(Mid(x,y))
        ret+=100;//中间的位置仅次于完整度
    int A=Corner(x,y,0);//获取当前位置是否在角落旁边和与其相邻的角落有多少空缺
    ret+=((5-A)*10)//空缺越少估价越高;
    return ret;
}
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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)||Evaluate(i,j)>Evaluate(x,y))
                    x=i,y=j,flag=1;
            }
        }
    int E=Evaluate(x,y);
    if(flag)
    {
        if((E/1000)%10==2)
            return 1;
        return 0;
    }//找千位数就可以知道是否完整了
    return flag;
}
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    int E=Evaluate(x,y);
    ret+=(5-(E/10)%10);
    Corner(x,y,1);//如果角落有空缺也要补上
    return ret;
}

然后就可以AC了，实际上最后10分也不需要200+排对吧QwQ

以下是完整代码（504排，比出题人写的题解大概少了60排吧，不压行好评QwQ）：

#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;
const int N=2000000+110;
const int inf=0x7fffffff;
const int MAXN=50;
const double eps=1e-8;
il int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
il void Getstr(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();
    }
}
int n,m,num,fr,tl;
int Hm,Hr,Hc,Hx,Hy;
int frz[MAXN][MAXN],f[MAXN][MAXN][MAXN];
int dx[]={0,0,0,0,1,-1};
int dy[]={0,0,1,-1,0,0};
int dz[]={1,-1,0,0,0,0};
bool perfect=1;
bool vis[MAXN][MAXN][MAXN];
struct node
{
    int x,y,z;
};
node q[MAXN];
il int Spell_Card(int x,int y,int dir,int s)
{
    int ret=0;
    for(ri i=0;i<=s;i++)
    {
        int Xi,Yi;
        switch(dir)
        {
            case 0:Xi=x-i,Yi=y;break;
            case 1:Xi=x-i,Yi=y-i;break;
            case 2:Xi=x,Yi=y-i;break;
            case 3:Xi=x+i,Yi=y-i;break;
            case 4:Xi=x+i,Yi=y;break;
            case 5:Xi=x+i,Yi=y+i;break;
            case 6:Xi=x,Yi=y+i;break;
            case 7:Xi=x-i,Yi=y+i;break;
        }
        if(Xi<0||Xi>=n||Yi<0||Yi>=n||frz[Xi][Yi]==inf)
            break;
        else if(frz[Xi][Yi]==4)
            continue;
        else
        {
            frz[Xi][Yi]++;
            ret++;
        }
    }
    return ret;
}
il int Make()
{
    int ret=0;
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
            if(frz[i][j]==4)
                frz[i][j]=0,ret++,num++;
    return ret;
}
il void Put(int r,int c,int h)
{
    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]&&!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)
            frz[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)
            frz[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)
            frz[r][c]=inf;
        return;
    }
}
il bool BFS(int r,int c,int h,int dir,bool last)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri 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]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
    {
        if(!last)
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0;
        else
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0,num++;
    }
    return flag;
}
il void Remove(int r,int c,int h)
{
    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)
            frz[r][c]=0;
        memset(f,-1,sizeof(f));
        int brk=0;
        for(ri i=0;i<6;i++)
        {
            int R=r+dx[i],C=c+dy[i],H=h+dz[i];
            if(f[R][C][H]!=-1||!vis[R][C][H])
                continue;
            else if(!BFS(R,C,H,i,0))
                brk+=fr;
            else
                continue;
        }
        printf("CIRNO REMOVED AN ICE_BLOCK");
        if(brk>0)
            printf(",AND %d BLOCK(S) ARE BROKEN",brk);
        printf("\n");
    }
}
il int Get_Height()
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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(ri k=Hm;k;k--)
                if(vis[i][j][k])
                {
                    h=k;
                    break;
                }
            ret=max(ret,h);
        }
    return ret+1;
}
il int Get_Need(int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
            if(!vis[i][j][h])
                vis[i][j][h]=1,ret++;
    return ret;
}
il bool Mid(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;
}
il int Corner(int x,int y,bool last)
{
    int ret=0;
    if((x==Hr&&y==Hc+1)||(x==Hr+1&&y==Hc))
    {
        for(ri 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(ri 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(ri 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(ri 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;
}
il int Evaluate(int x,int y)
{
    int ret=0;
    for(ri i=0;i<2;i++)
        if(!vis[x][y][i])
            ret+=1000;
    if(Mid(x,y))
        ret+=100;
    int A=Corner(x,y,0);
    ret+=((5-A)*10);
    return ret;
}
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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)||Evaluate(i,j)>Evaluate(x,y))
                    x=i,y=j,flag=1;
            }
        }
    int E=Evaluate(x,y);
    if(flag)
    {
        if((E/1000)%10==2)
            return 1;
        return 0;
    }
    return flag;
}
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri 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(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    int E=Evaluate(x,y);
    ret+=(5-(E/10)%10);
    Corner(x,y,1);
    return ret;
}
il int Check_Corner(int h)
{
    int ret=0;
    for(ri 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;
}
il void Fix(int h)
{
    bool door=0,corner=0;
    int x=-1,y=-1;
    door=Check_Door(x,y);
    if(x!=-1&&y!=-1)
    {
        int E=Evaluate(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");
}
il void Remove_Blocks(int h)
{
    memset(f,-1,sizeof(f));
    if(!BFS(Hr,Hc,h,0,1))
    {
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n");
        return;
    }
    int dir=1;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            for(ri k=0;k<h;k++)
                if(vis[i][j][k]&&f[i][j][k]==-1)
                    BFS(i,j,k,dir++,1);
        }
    Fix(h);
}
il void Make_Roof()
{
    int h=Get_Height();
    int need=Get_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(ri i=Hr+1;i<=Hr+Hx-2;i++)
        for(ri j=Hc+1;j<=Hc+Hy-2;j++)
        {
            for(ri k=0;k<h;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num1++,num++,perfect=0;
            for(ri k=h+1;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;
        }
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
        {
            if(i>=Hr&&i<=Hr+Hx-1&&j>=Hc&&j<=Hc+Hy-1)
                continue;
            for(ri 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_Blocks(h);
}
int main()
{
    n=read();
    Hm=read();
    Hr=read(),Hc=read(),Hx=read(),Hy=read();
    m=read();
    for(ri i=1;i<=m;i++)
    {
        char opt[MAXN];
        memset(opt,0,sizeof(opt));
        Getstr(opt);
        if(strcmp(opt,"ICE_BARRAGE")==0)
        {
            int r=read(),c=read(),dir=read(),s=read();
            printf("CIRNO FREEZED %d BLOCK(S)\n",Spell_Card(r,c,dir,s));
        }
        else if(strcmp(opt,"MAKE_ICE_BLOCK")==0)
        {
            int k=Make();
            printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S)\n",k,num);
        }
        else if(strcmp(opt,"PUT_ICE_BLOCK")==0)
        {
            int r=read(),c=read(),h=read();
            Put(r,c,h);
        }
        else if(strcmp(opt,"REMOVE_ICE_BLOCK")==0)
        {
            int r=read(),c=read(),h=read();
            Remove(r,c,h);
        }
        else
            Make_Roof();
    }
    return 0;
}

P3693 琪露诺的冰雪小屋 题解

P3693 琪露诺的冰雪小屋题解