ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解

@失踪人口回归-乙酸王
好吧现在开始叫我乙酸王好了

前言

自从去年10月失踪后神秘复活（不好意思搞Android去了，壳烯App马..马..马上上线..请各位不要在我打游戏时催更了好嘛....）

顶着学校招生办和年纪主任的压力在NOIP自闭的情况下交了800块钱给报了这个什么ACSL（如题）？？？（还不是招生办威逼利诱？？？）

说正经的，这题目深搜？？？DP？？？
不存在的
我乙酸王一辈子就没打过深搜和DP
那就暴力过吧

题目索引 [ 题目我是没找着，老师给的paper]

ASCL官网

题面如下

源自拉丁方块拼图类型。摩天大楼是日本人发明的。1992年，出版商Sekai Bunka-sha在纽约举办的第一届世界益智锦标赛上向参赛者展示了一本20页的英文版益智杂志。在美国凯文•斯通(Kevin Stone)加强了这一点。

每个谜题由一个NxN的网格，网格两侧有一些线索。下面的问题将会使用如下图所示的4x4网格。其目的是在每个格子上都安置一座摩天大楼，高度从1到4不等。因此，没有两座摩天大楼在一排或一列有相同的高度。另一个给定的线索是网格外围的数字，表示从此处的方向可以看到的摩天大楼的数量。

图片发自简书App

在上面的从左到右摆放的四个摩天大楼的例子中，用堆叠的矩形表示摩天大楼，从左边往右看，您可以看到#2、#3和#4摩天大楼。1号摩天大楼被3号摩天大楼挡住了。从右边往左看，4号摩天大楼挡住了所有其他的摩天大楼。因此线索数是3和1。

输入格式

将会有6行输入。
第一行由6个数字字符串，代表一行的数字和线索。其中第一个和最后一个字符串有4个字符，表示最顶端和最底端的线索。其他的4个字符串有6个或2个字符，2个的表示一行的左边和右边的线索，6个的表示这一行从左到右的线索和网格中的数字。

输入输出样例

样例.png

暴力出奇迹骗分过样例

题目分析

无脑题一个
没有思路

边上（线索）为 1 的，则临近的一个一定为 4号楼
边上（线索）为 4 的，则从临近的一个开始 1,2,3,4四栋楼一溜排开
然后你就会发现有的溜已经有三栋楼了
那么你就只需要填唯一一座楼了

复杂度

一共就 6*6 的int 不管复杂度了

1.数据准备

int maps[6][6];
//用于保存房屋数据 
//[0][]为最上方的线索 其他同理
//[1-4][1-4]为房屋编号

2.读入数据

注意： ***的程序员居然出这种数据的题目？？惊了
第一行数据用“，”分开
小数据中间不带空格的亲

那么就..先把第一行数据拆开把，其他五行是query需求，先不管

void initData(){
    string str="";
    cin>>str;
    string str_k="";
    int vk=0;
    for(int i=0;i<str.length();i++){
        if(str[i]==','){
            savemaps(str_k,vk++);
            str_k="";
        }else{
            str_k+=str[i];
        }
    }
    savemaps(str_k,vk);
}

savempas()?
介是用来在创建maps时保存无脑的string数据的？
好吧就是把一溜string保存为int 的maps

void savemaps(string str,int k){
     //if(DEBUG)cout<<"savemaps() str="<<str<<"  k="<<k<<endl;  
     if(k==0||k==5){
        for(int i=1;i<5;i++){
            maps[k][i]=str[i-1]-'0';
            if(maps[k][i]==4||maps[k][i]==1){
                setLine(maps[k][i],k,i);
            }
        }
     }else if(str.length()==6){
        for(int i=0;i<6;i++){
            maps[k][i]=str[i]-'0';
            if((i==0||i==5)&&(maps[k][i]==4||maps[k][i]==1)){
                setLine(maps[k][i],k,i);
            }
        }
     }else{
        maps[k][0]=str[0]-'0';
        if(maps[k][0]==4||maps[k][0]==1){
            setLine(maps[k][0],k,0);
        }
        maps[k][5]=str[1]-'0';
        if(maps[k][5]==4||maps[k][5]==1){
            setLine(maps[k][5],k,5);
        }
     }
}

setLine()便是我们暴力的开始了
将线索为1、4的一溜先给填上

void setLine(int isLine,int li,int ro){
    //if(DEBUG)cout<<"setLine() isLine="<<isLine<<"  li="<<li<<"  ro="<<ro<<endl;   
    if(isLine==4){// 1,2,3,4
        if(ro==0){
            for(int i=1;i<5;i++){
                maps[li][i]=i;
            }
        }else if(ro==5){
            for(int i=4;i>0;i--){
                maps[li][i]=4-i+1;
            }
        }else if(li==0){
            for(int i=1;i<5;i++){
                maps[i][ro]=i;
            }
        }else if(li==5){
            for(int i=4;i>0;i--){
                maps[i][ro]=4-i+1;
            }
        }
    }else{// 4
        if(li==0){
            maps[1][ro]=4;
        }else if(li==5){
            maps[4][ro]=4;
        }else if(ro==0){
            maps[li][1]=4;
        }else if(ro==5){
            maps[li][4]=4;
        }
    }
}

3.CreatMaps

读个数据进来不容易啊
读的时候顺便暴力的初始化了一下maps，那么现在就很简单了的啦

用一个浅搜去寻找每一个只剩一个空的地方
是的，浅搜，不是深搜

void creatMaps(){
    bool es[5]={0,0,0,0,0};
    for(int i=1;i<5;i++){//检查一行 
        if(isNeedOnlyOne(i,1)){//如果这一溜剩一个空
            FillLine(i,1);//填它
        }
    }
    for(int i=1;i<5;i++){//检查一列 
        if(isNeedOnlyOne(i,0)){
            FillLine(i,0);
        }
    }
    if(!checkFull()){
        creatMaps();
    }
}

我也觉得写复杂了
可是我 ~~作业没写完~~ 懒所以..
并不打算改

bool isNeedOnlyOne(int k,int tp){//tp==1 行
    //if(DEBUG)cout<<"isNeedOnlyOne()"<<endl;   
    int sum=0; 
    if(tp==1){
        for(int i=1;i<5;i++){
            if(maps[k][i]==0){
                sum++;
            }
            if(sum>1){
                return false;
            }
        }
    }else{
        for(int i=1;i<5;i++){
            if(maps[i][k]==0){
                sum++;
            }
            if(sum>1){
                return false;
            }
        }
    }
    return true;
}
int GetRest(int p1,int p2,int p3,int p4){//在1,2,3,4里找剩下的一个需要这么写吗？？？
    bool es[5]={0,0,0,0,0};
    es[p1]=1;
    es[p2]=1;
    es[p3]=1;
    es[p4]=1;
    for(int i=1;i<5;i++){
        if(!es[i])
            return i;
    }
}
void FillLine(int k,int tp){//tp==1 行 
    //if(DEBUG)cout<<"FillLine()"<<endl;    
    //一定只剩一个要填才会进入此函数
    bool es[5]={0,0,0,0,0};
    int ord=0;
    if(tp==1){
        for(int i=1;i<5;i++){
            if(maps[k][i]==0){
                maps[k][i]=GetRest(maps[k][1],maps[k][2],maps[k][3],maps[k][4]);
            }
        }
    }else{
        for(int i=1;i<5;i++){
            if(maps[i][k]==0){
                maps[i][k]=GetRest(maps[1][k],maps[2][k],maps[3][k],maps[4][k]);
            }
        }
    }
}

4.找答案

maps已经就绪，还剩下五行输入的亲
然后就直接找着答案输出了啦
懒惰的我直接封装了一个query(string )的函数？？

int query(string pos){
    int line=pos[0]-'0';
    int row=pos[1]-'0';
    return maps[line][row];
}

5.主函数

int main(){
    initData();
    creatMaps();
    string que="";
    for(int i=0;i<5;i++){
        cin>>que;
        cout<<query(que)<<endl;
    }
    return 0;
}

全部代码

~~(快捷复制：按住鼠标左键选择你要的代码然后Ctrl+c)~~

#include <bits/stdc++.h>
using namespace std;
const bool DEBUG=true;

int maps[6][6];
void setLine(int isLine,int li,int ro){
    //if(DEBUG)cout<<"setLine() isLine="<<isLine<<"  li="<<li<<"  ro="<<ro<<endl;   
    if(isLine==4){// 1,2,3,4
        if(ro==0){
            for(int i=1;i<5;i++){
                maps[li][i]=i;
            }
        }else if(ro==5){
            for(int i=4;i>0;i--){
                maps[li][i]=4-i+1;
            }
        }else if(li==0){
            for(int i=1;i<5;i++){
                maps[i][ro]=i;
            }
        }else if(li==5){
            for(int i=4;i>0;i--){
                maps[i][ro]=4-i+1;
            }
        }
    }else{// 4
        if(li==0){
            maps[1][ro]=4;
        }else if(li==5){
            maps[4][ro]=4;
        }else if(ro==0){
            maps[li][1]=4;
        }else if(ro==5){
            maps[li][4]=4;
        }
    }
}
void savemaps(string str,int k){
     //if(DEBUG)cout<<"savemaps() str="<<str<<"  k="<<k<<endl;  
     if(k==0||k==5){
        for(int i=1;i<5;i++){
            maps[k][i]=str[i-1]-'0';
            if(maps[k][i]==4||maps[k][i]==1){
                setLine(maps[k][i],k,i);
            }
        }
     }else if(str.length()==6){
        for(int i=0;i<6;i++){
            maps[k][i]=str[i]-'0';
            if((i==0||i==5)&&(maps[k][i]==4||maps[k][i]==1)){
                setLine(maps[k][i],k,i);
            }
        }
     }else{
        maps[k][0]=str[0]-'0';
        if(maps[k][0]==4||maps[k][0]==1){
            setLine(maps[k][0],k,0);
        }
        maps[k][5]=str[1]-'0';
        if(maps[k][5]==4||maps[k][5]==1){
            setLine(maps[k][5],k,5);
        }
     }
}
void initData(){
    string str="";
    cin>>str;
    string str_k="";
    int vk=0;
    for(int i=0;i<str.length();i++){
        if(str[i]==','){
            savemaps(str_k,vk++);
            str_k="";
        }else{
            str_k+=str[i];
        }
    }
    savemaps(str_k,vk);
}

int query(string pos){
    int line=pos[0]-'0';
    int row=pos[1]-'0';
    return maps[line][row];
}
bool checkFull(){
    //if(DEBUG)cout<<"checkFull()"<<endl;   
    for(int i=1;i<5;i++)
        for(int j=1;j<5;j++){
            if(maps[i][j]==0)
                return false;
        }
    return true;
}
bool isNeedOnlyOne(int k,int tp){//tp==1 行
    //if(DEBUG)cout<<"isNeedOnlyOne()"<<endl;   
    int sum=0; 
    if(tp==1){
        for(int i=1;i<5;i++){
            if(maps[k][i]==0){
                sum++;
            }
            if(sum>1){
                return false;
            }
        }
    }else{
        for(int i=1;i<5;i++){
            if(maps[i][k]==0){
                sum++;
            }
            if(sum>1){
                return false;
            }
        }
    }
    return true;
}
int GetRest(int p1,int p2,int p3,int p4){
    bool es[5]={0,0,0,0,0};
    es[p1]=1;
    es[p2]=1;
    es[p3]=1;
    es[p4]=1;
    for(int i=1;i<5;i++){
        if(!es[i])
            return i;
    }
}
void FillLine(int k,int tp){//tp==1 行 
    //if(DEBUG)cout<<"FillLine()"<<endl;    
    //一定只剩一个要填才会进入此函数
    bool es[5]={0,0,0,0,0};
    int ord=0;
    if(tp==1){
        for(int i=1;i<5;i++){
            if(maps[k][i]==0){
                maps[k][i]=GetRest(maps[k][1],maps[k][2],maps[k][3],maps[k][4]);
            }
        }
    }else{
        for(int i=1;i<5;i++){
            if(maps[i][k]==0){
                maps[i][k]=GetRest(maps[1][k],maps[2][k],maps[3][k],maps[4][k]);
            }
        }
    }
}
void creatMaps(){
    bool es[5]={0,0,0,0,0};
    for(int i=1;i<5;i++){//检查一行 
        if(isNeedOnlyOne(i,1)){
            FillLine(i,1);
        }
    }
    for(int i=1;i<5;i++){//检查一列 
        if(isNeedOnlyOne(i,0)){
            FillLine(i,0);
        }
    }
    if(!checkFull()){
        creatMaps();
    }
}
void showMaps(){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            cout<<maps[i][j]<<" ";
        }
        cout<<endl;
    }
}
/*
3221,41,22,14,231422,2313

*/
int main(){
    initData();
    //cout<<"initData() Successfully!"<<endl;
    //showMaps();
    creatMaps();
    //cout<<"show map after creatMaps()!!!"<<endl;
    //showMaps();
    string que="";
    for(int i=0;i<5;i++){
        cin>>que;
        cout<<query(que)<<endl;
    }
    return 0;
}

Release 2019.4.13 16:44 By HaoDaDaDa
Update 2019.4.14 12:32 By HaoDaDaDa

最后编辑于：2019.04.14 12:32:46

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,607评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,047评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,496评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,405评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,400评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,479评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,883评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,535评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,743评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,544评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,612评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,309评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,881评论 3赞 306
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,891评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,136评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,783评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,316评论 2赞 342