【洛谷P3693】琪露诺的冰雪小屋
mrsrz
10月 24, 2019
模拟
题目大意：
题解：
一年前就写了，现在数据加强了，然后以前的代码过不了了……
模拟题。好像又是没啥好说类型。
前几个操作都比较简单的，注意细节即可。
就说一下最后一个操作。
首先造屋顶。题目中说屋顶可能触及平面 HM，因此判连通性的时候要注意判到 HM。
接下来是去掉多余方块，这里没什么问题。
然后是找门……这里和补墙是有联系的，需要先找对门才能补墙。所以我们来看看补墙。
中间的块显然是直接补的，关键是角落的块。只有被定义为“残缺”的角落块，才需要被补上。
观察补墙的规则，需要使得填上后不存在肉眼可见的“残缺”的墙。
注意到，此时门还没安上，因此计划要放门的位置的方块得原封不动。
那么一个角落上的块需要被填补，当且仅当它旁边的位置预留给门，并且原来没有方块。如果原来有方块，那么此时还无需被拆除，所以它旁边的角落不需要被补上。我原来错的原因就是只判角落旁边是不是门，而没有考虑其原来是否有方块。
我们已经得到填补墙的正确策略了，接下来可以找门了。
首先，门的位置需要拆掉的方块尽可能少；其次，要保证用来填补角落的方块的耗费尽可能少；最后，尽可能开在中间。
按照这个策略找一扇门即可。
之后的操作还是比较简单的，按题意模拟即可。
Code：
/*
By mrsrz
2018-10-17
update on 2019-10-19 ~ 2019-10-24
*/
#include<bits/stdc++.h>
using namespace std;
int N,HM,HR,HC,HX,HY,M;
int block[25][25][25];//每个位置有没有砖块
int cold[25][25];//冷冻度
int Have_Blocks=0;//有的砖块个数
struct _3D{
int x,y,z;
};
int dx[]={0,1,0,-1,0,0},dy[]={1,0,-1,0,0,0},dz[]={0,0,0,0,1,-1};
queue<_3D>q;
int ok[25][25][25];//判断是否连通
void bfs(){
memset(ok,0,sizeof ok);
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
if(block[i][j][0]){
ok[i][j][0]=1;
q.push((_3D){i,j,0});
}
while(!q.empty()){
_3D now=q.front();q.pop();
for(int i=0;i<6;++i){
_3D to=(_3D){now.x+dx[i],now.y+dy[i],now.z+dz[i]};
if(to.x<0||to.y<0||to.z<0||to.x>=N||to.y>=N||to.z>HM)continue;
if(block[to.x][to.y][to.z]&&!ok[to.x][to.y][to.z]){
ok[to.x][to.y][to.z]=1;
q.push(to);
}
}
}
}
namespace ICE_BARRAGE{//发射弹幕
int R,C,D,S;
const int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,-1,-1,-1,0,1,1,1};
void main(){
cin>>R>>C>>D>>S;
++S;
int Success=0;//成功增加冷冻度的方块数
while(S--){
if(R<0||C<0||R>=N||C>=N)break;
if(block[R][C][0])break;
if(cold[R][C]<4)++cold[R][C],++Success;
R+=dx[D],C+=dy[D];
}
cout<<"CIRNO FREEZED "<<Success<<" BLOCK(S)";
}
}
namespace MAKE_ICE_BLOCK{//收集砖块
void main(){
int added=0;//增加的个数
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
if(cold[i][j]==4){
cold[i][j]=0;
++added;
}
Have_Blocks+=added;
cout<<"CIRNO MADE "<<added<<" ICE BLOCK(S),NOW SHE HAS "<<Have_Blocks<<" ICE BLOCK(S)\n";
}
}
namespace PUT_ICE_BLOCK{//放砖块
int R,C,H;
void main(){
cin>>R>>C>>H;
if(!Have_Blocks){
cout<<"CIRNO HAS NO ICE_BLOCK\n";
return;
}
bfs();
bool canput=false;//判断是否能放
if(H==0)canput=true;else
for(int i=0;i<6;++i){
int x=R+dx[i],y=C+dy[i],z=H+dz[i];
if(x<0||y<0||z<0||x>=N||y>=N||z>=HM)continue;
if(ok[x][y][z])canput=true;
}
if(!canput||block[R][C][H]){
cout<<"BAKA CIRNO,CAN'T PUT HERE\n";
return;
}
block[R][C][H]=1;--Have_Blocks;
if(H==0)cold[R][C]=0;//!高度为0时放置要清空冷冻度
if(R<HR||R>HR+HX-1||C<HC||C>HC+HY-1){
cout<<"CIRNO MISSED THE PLACE\n";
}else
if(HR+1<=R&&R<=HR+HX-2&&HC+1<=C&&C<=HC+HY-2){
cout<<"CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE\n";
}else{
cout<<"CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS "<<Have_Blocks
<<" ICE_BLOCK(S)\n";
}
}
}
namespace REMOVE_ICE_BLOCK{//移除砖块
int R,C,H;
void main(){
cin>>R>>C>>H;
if(!block[R][C][H]){
cout<<"BAKA CIRNO,THERE IS NO ICE_BLOCK\n";
return;
}
block[R][C][H]=0;
++Have_Blocks;
cout<<"CIRNO REMOVED AN ICE_BLOCK";
bfs();
int broke=0;//摔碎了的砖块数量
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
for(int k=0;k<HM;++k)
if(block[i][j][k]&&!ok[i][j][k]){
++broke;
block[i][j][k]=0;
}
if(broke)
cout<<",AND "<<broke<<" BLOCK(S) ARE BROKEN";
cout<<'\n';
}
}
namespace MAKE_ROOF{//建屋顶
int WALL_HIGH;
int gethigh(){//获取墙高
int maxh=0;
for(int i=0;i<HX;++i)
for(int h=HM;~h;--h){
if(block[HR+i][HC][h])
maxh=max(maxh,h);
if(block[HR+i][HC+HY-1][h])
maxh=max(maxh,h);
}
for(int i=0;i<HY;++i)
for(int h=HM;~h;--h){
if(block[HR][HC+i][h])
maxh=max(maxh,h);
if(block[HR+HX-1][HC+i][h])
maxh=max(maxh,h);
}
return maxh;
}
int ready(int h){//已经有砖块的格子数
int ret=0;
for(int i=HR;i<HR+HX;++i)
for(int j=HC;j<HC+HY;++j)
ret+=block[i][j][h];
return ret;
}
struct sort_data{
pair<int,int>zb;
int h1,h2,h3;
inline bool operator<(const sort_data&rhs)const{
if(h1!=rhs.h1)return h1>rhs.h1;
if(h2!=rhs.h2)return h2<rhs.h2;
return h3>rhs.h3;
}
};
vector<sort_data>vec;
inline int get_blocks_to_fix_the_wall(pair<int,int>door,int fixit=0){
int use_to_fix_wall=0;//用来修补的砖块
for(int i=1;i<HX-1;++i)
for(int h=0;h<=WALL_HIGH;++h){
if(!block[HR+i][HC][h]&&!(HR+i==door.first&&HC==door.second&&h<2)){
block[HR+i][HC][h]=fixit;
++use_to_fix_wall;
}
if(!block[HR+i][HC+HY-1][h]&&!(HR+i==door.first&&HC+HY-1==door.second&&h<2)){
block[HR+i][HC+HY-1][h]=fixit;
++use_to_fix_wall;
}
}
for(int i=1;i<HY-1;++i)
for(int h=0;h<=WALL_HIGH;++h){
if(!block[HR][HC+i][h]&&!(HR==door.first&&HC+i==door.second&&h<2)){
block[HR][HC+i][h]=fixit;
++use_to_fix_wall;
}
if(!block[HR+HX-1][HC+i][h]&&!(HR+HX-1==door.first&&HC+i==door.second&&h<2)){
block[HR+HX-1][HC+i][h]=fixit;
++use_to_fix_wall;
}
}
//修补除了角落的墙壁
if(fixit==0)use_to_fix_wall=0;
for(int h=0;h<=WALL_HIGH&&h<2;++h){//对角落进行考虑
if(!block[HR][HC][h]&&(door.first==HR+1&&door.second==HC&&!block[HR+1][HC][h]||door.first==HR&&door.second==HC+1&&!block[HR][HC+1][h])){
block[HR][HC][h]=fixit;
++use_to_fix_wall;
}
if(!block[HR][HC+HY-1][h]&&(door.first==HR+1&&door.second==HC+HY-1&&!block[HR+1][HC+HY-1][h]||door.first==HR&&door.second==HC+HY-2&&!block[HR][HC+HY-2][h])){
block[HR][HC+HY-1][h]=fixit;
++use_to_fix_wall;
}
if(!block[HR+HX-1][HC][h]&&(door.first==HR+HX-2&&door.second==HC&&!block[HR+HX-2][HC][h]||door.first==HR+HX-1&&door.second==HC+1&&!block[HR+HX-1][HC+1][h])){
block[HR+HX-1][HC][h]=fixit;
++use_to_fix_wall;
}
if(!block[HR+HX-1][HC+HY-1][h]&&(door.first==HR+HX-2&&door.second==HC+HY-1&&!block[HR+HX-2][HC+HY-1][h]||door.first==HR+HX-1&&door.second==HC+HY-2&&!block[HR+HX-1][HC+HY-2][h])){
block[HR+HX-1][HC+HY-1][h]=fixit;
++use_to_fix_wall;
}
}
return use_to_fix_wall;
}
pair<int,int>getdoor(int MAX){//找门的位置
vec.clear();
for(int i=HC+1;i<=HC+HY-2;++i){//HR
pair<int,int>zb=make_pair(HR,i);
int h3=1;
if(HY&1){
if(i!=(HC+HC+HY-1>>1))h3=0;
}else{
if(i!=(HC+HC+HY-1>>1)||i!=(HC+HC+HY-1>>1)+1)h3=0;
}
vec.push_back((sort_data){zb,!block[HR][i][0]+!block[HR][i][1],get_blocks_to_fix_the_wall(zb),h3});
}
for(int i=HC+1;i<=HC+HY-2;++i){//HR+HX-1
pair<int,int>zb=make_pair(HR+HX-1,i);
int h3=1;
if(HY&1){
if(i!=(HC+HC+HY-1>>1))h3=0;
}else{
if(i!=(HC+HC+HY-1>>1)&&i!=(HC+HC+HY-1>>1)+1)h3=0;
}
vec.push_back((sort_data){zb,!block[HR+HX-1][i][0]+!block[HR+HX-1][i][1],get_blocks_to_fix_the_wall(zb),h3});
}
for(int i=HR+1;i<=HR+HX-2;++i){//HC
pair<int,int>zb=make_pair(i,HC);
int h3=1;
if(HX&1){
if(i!=(HR+HR+HX-1>>1))h3=0;
}else{
if(i!=(HR+HR+HX-1>>1)&&i!=(HR+HR+HX-1>>1)+1)h3=0;
}
vec.push_back((sort_data){zb,!block[i][HC][0]+!block[i][HC][1],get_blocks_to_fix_the_wall(zb),h3});
}
for(int i=HR+1;i<=HR+HX-2;++i){//HC+HY-1
pair<int,int>zb=make_pair(i,HC+HY-1);
int h3=1;
if(HX&1){
if(i!=(HR+HR+HX-1>>1))h3=0;
}else{
if(i!=(HR+HR+HX-1>>1)&&i!=(HR+HR+HX-1>>1)+1)h3=0;
}
vec.push_back((sort_data){zb,!block[i][HC+HY-1][0]+!block[i][HC+HY-1][1],get_blocks_to_fix_the_wall(zb),h3});
}
sort(vec.begin(),vec.end());
// for(int i=0;i<vec.size();++i)
// if(vec[i].h2<=MAX)
// return vec[i].zb;
return vec[0].zb;
}
void main(){
WALL_HIGH=gethigh();//墙的最高高度
int ROOF_HIGH=WALL_HIGH+1;//屋顶的高度
int need=HX*HY-ready(ROOF_HIGH);//需要用来建屋顶的砖块数量
if(Have_Blocks<need){
cout<<"SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF\n";
return;
}
if(WALL_HIGH<1||((HX-2)*(HY-2)*(WALL_HIGH+1)<2)||HX<2||HY<2){
cout<<"SORRY CIRNO,HOUSE IS TOO SMALL\n";
return;
}
Have_Blocks-=need;
for(int i=HR;i<HR+HX;++i)
for(int j=HC;j<HC+HY;++j)
block[i][j][ROOF_HIGH]=1;
int inside=0,outside=0;//内部移除的砖块、外部的砖块
for(int i=HR+1;i<HR+HX-1;++i)
for(int j=HC+1;j<HC+HY-1;++j)
for(int k=0;k<=WALL_HIGH;++k)
if(block[i][j][k]){//计算内部拆掉的砖块
block[i][j][k]=0;
++inside;
}
cout<<inside<<" ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED\n";
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))
for(int k=0;k<=HM;++k)
if(block[i][j][k]){
++outside;
}else;else
for(int k=ROOF_HIGH+1;k<=HM;++k)
if(block[i][j][k]){
++outside;
}
cout<<outside<<" ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED\n";
bfs();
for(int i=HR;i<HR+HX;++i)
for(int j=HC;j<HC+HY;++j)
if(block[i][j][ROOF_HIGH]&&!ok[i][j][ROOF_HIGH]){//判断屋顶是否会塌
cout<<"SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n";
return;
}
Have_Blocks+=inside+outside;
pair<int,int>door=getdoor(Have_Blocks);
// cout<<door.first<<' '<<door.second<<endl;
int use_to_fix_wall=get_blocks_to_fix_the_wall(door,1);
if(Have_Blocks<use_to_fix_wall){
cout<<"SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL\n";
return;
}
Have_Blocks-=use_to_fix_wall;
bool is_fix_door=0;
cout<<"GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE\n";
if(!block[door.first][door.second][0]&&!block[door.first][door.second][1]){
cout<<"DOOR IS OK\n";
}else{
is_fix_door=1;
cout<<"HOUSE HAS NO DOOR\n";
Have_Blocks+=block[door.first][door.second][0]+block[door.first][door.second][1];
block[door.first][door.second][0]=block[door.first][door.second][1]=0;
}
if(use_to_fix_wall)cout<<"WALL NEED TO BE FIXED\n";else
cout<<"WALL IS OK\n";
//下面开始补柱子
int use_to_fix_corner=0;
for(int h=0;h<=WALL_HIGH;++h){
if(!block[HR][HC][h]){
block[HR][HC][h]=1;
++use_to_fix_corner;
}
if(!block[HR][HC+HY-1][h]){
block[HR][HC+HY-1][h]=1;
++use_to_fix_corner;
}
if(!block[HR+HX-1][HC][h]){
block[HR+HX-1][HC][h]=1;
++use_to_fix_corner;
}
if(!block[HR+HX-1][HC+HY-1][h]){
block[HR+HX-1][HC+HY-1][h]=1;
++use_to_fix_corner;
}
}
if(use_to_fix_corner){
cout<<"CORNER NEED TO BE FIXED\n";
if(Have_Blocks<use_to_fix_corner)Have_Blocks=0;else
Have_Blocks-=use_to_fix_corner;
}else{
cout<<"CORNER IS OK\n";
}
cout<<"CIRNO FINALLY HAS "<<Have_Blocks<<" ICE_BLOCK(S)\n";
//下面判完美情况
if(!use_to_fix_wall&&!use_to_fix_corner&&!is_fix_door&&!inside&&!outside){
bool ok=true;
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
for(int k=0;k<HM;++k){
if((i==HR||i==HR+HX-1)&&(HC<=j&&j<=HC+HY-1)||(j==HC||j==HC+HY-1)&&(HR<=i&&i<=HR+HX-1)){//墙上方有砖块
if(k>ROOF_HIGH&&block[i][j][k]){
ok=false;break;
}
}else
if(!(HR<=i&&i<=HR+HX-1&&HC<=j&&j<=HC+HY-1&&k==ROOF_HIGH)&&block[i][j][k]){//非屋顶有砖块
ok=false;break;
}
}
//以下判断门是否放在中间
if(door.first==HR||door.first==HR+HX-1){
if(HY&1){//奇数
if(door.second!=(HC+HC+HY-1>>1))ok=false;
}else{//偶数
if(door.second!=(HC+HC+HY-1>>1)&&door.second!=(HC+HC+HY-1>>1)+1)ok=false;
}
}else{
if(HX&1){//奇数
if(door.first!=(HR+HR+HX-1>>1))ok=false;
}else{//偶数
if(door.first!=(HR+HR+HX-1>>1)&&door.first!=(HR+HR+HX-1>>1)+1)ok=false;
}
}
if(ok)
cout<<"CIRNO IS PERFECT!\n";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin>>N>>HM>>HR>>HC>>HX>>HY>>M;
for(int i=1;i<=M;++i){
string opt;
cin>>opt;
if(opt=="ICE_BARRAGE")ICE_BARRAGE::main();else
if(opt=="MAKE_ICE_BLOCK")MAKE_ICE_BLOCK::main();else
if(opt=="PUT_ICE_BLOCK")PUT_ICE_BLOCK::main();else
if(opt=="REMOVE_ICE_BLOCK")REMOVE_ICE_BLOCK::main();else
if(opt=="MAKE_ROOF")MAKE_ROOF::main();
if(opt=="ICE_BARRAGE")cout<<'\n';
}
return 0;
}