ACSL 美國計(jì)算機(jī)科學(xué)聯(lián)賽 2016-2017 R4 摩天大樓-Skyscraper 題解

@失蹤人口回歸-乙酸王
好吧現(xiàn)在開始叫我乙酸王好了

前言

自從去年10月失蹤后神秘復(fù)活（不好意思搞Android去了托享，殼烯App馬..馬..馬上上線..請各位不要在我打游戲時(shí)催更了好嘛....）

頂著學(xué)校招生辦和年紀(jì)主任的壓力在NOIP自閉的情況下交了800塊錢給報(bào)了這個(gè)什么ACSL（如題）？借嗽？？（還不是招生辦威逼利誘裁蚁？设凹？？）

說正經(jīng)的娃承，這題目深搜？怕篷？历筝？DP？廊谓？梳猪？
不存在的
我乙酸王一輩子就沒打過深搜和DP
那就暴力過吧

題目索引 [ 題目我是沒找著，老師給的paper]

題面如下

源自拉丁方塊拼圖類型蹂析。摩天大樓是日本人發(fā)明的舔示。1992年，出版商Sekai Bunka-sha在紐約舉辦的第一屆世界益智錦標(biāo)賽上向參賽者展示了一本20頁的英文版益智雜志电抚。在美國凱文?斯通(Kevin Stone)加強(qiáng)了這一點(diǎn)惕稻。

每個(gè)謎題由一個(gè)NxN的網(wǎng)格，網(wǎng)格兩側(cè)有一些線索蝙叛。下面的問題將會(huì)使用如下圖所示的4x4網(wǎng)格俺祠。其目的是在每個(gè)格子上都安置一座摩天大樓，高度從1到4不等借帘。因此蜘渣，沒有兩座摩天大樓在一排或一列有相同的高度。另一個(gè)給定的線索是網(wǎng)格外圍的數(shù)字肺然，表示從此處的方向可以看到的摩天大樓的數(shù)量蔫缸。

圖片發(fā)自簡書App

在上面的從左到右擺放的四個(gè)摩天大樓的例子中，用堆疊的矩形表示摩天大樓际起，從左邊往右看拾碌，您可以看到#2、#3和#4摩天大樓街望。1號摩天大樓被3號摩天大樓擋住了校翔。從右邊往左看，4號摩天大樓擋住了所有其他的摩天大樓灾前。因此線索數(shù)是3和1防症。

輸入格式

將會(huì)有6行輸入。
第一行由6個(gè)數(shù)字字符串，代表一行的數(shù)字和線索蔫敲。其中第一個(gè)和最后一個(gè)字符串有4個(gè)字符饲嗽，表示最頂端和最底端的線索。其他的4個(gè)字符串有6個(gè)或2個(gè)字符燕偶，2個(gè)的表示一行的左邊和右邊的線索喝噪，6個(gè)的表示這一行從左到右的線索和網(wǎng)格中的數(shù)字。

輸入輸出樣例

樣例.png

暴力出奇跡騙分過樣例

題目分析

無腦題一個(gè)
沒有思路

邊上（線索）為 1 的指么，則臨近的一個(gè)一定為 4號樓
邊上（線索）為 4 的，則從臨近的一個(gè)開始 1,2,3,4四棟樓一溜排開
然后你就會(huì)發(fā)現(xiàn)有的溜已經(jīng)有三棟樓了
那么你就只需要填唯一一座樓了

復(fù)雜度

一共就 6*6 的int 不管復(fù)雜度了

1.數(shù)據(jù)準(zhǔn)備

int maps[6][6];
//用于保存房屋數(shù)據(jù) 
//[0][]為最上方的線索 其他同理
//[1-4][1-4]為房屋編號

2.讀入數(shù)據(jù)

注意： ***的程序員居然出這種數(shù)據(jù)的題目榴鼎？伯诬？驚了
第一行數(shù)據(jù)用“，”分開
小數(shù)據(jù)中間不帶空格的親

那么就..先把第一行數(shù)據(jù)拆開把巫财，其他五行是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()?
介是用來在創(chuàng)建maps時(shí)保存無腦的string數(shù)據(jù)的？
好吧就是把一溜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

讀個(gè)數(shù)據(jù)進(jìn)來不容易啊
讀的時(shí)候順便暴力的初始化了一下maps赫舒，那么現(xiàn)在就很簡單了的啦

用一個(gè)淺搜去尋找每一個(gè)只剩一個(gè)空的地方
是的，淺搜闽瓢，不是深搜

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

我也覺得寫復(fù)雜了
可是我 ~~作業(yè)沒寫完~~ 懶所以..
并不打算改

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里找剩下的一個(gè)需要這么寫嗎接癌？？扣讼？
    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;    
    //一定只剩一個(gè)要填才會(huì)進(jìn)入此函數(shù)
    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已經(jīng)就緒缺猛，還剩下五行輸入的親
然后就直接找著答案輸出了啦
懶惰的我直接封裝了一個(gè)query(string )的函數(shù)？椭符？

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

5.主函數(shù)

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

全部代碼

~~(快捷復(fù)制：按住鼠標(biāo)左鍵選擇你要的代碼然后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;    
    //一定只剩一個(gè)要填才會(huì)進(jìn)入此函數(shù)
    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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末荔燎，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子销钝，更是在濱河造成了極大的恐慌有咨，老刑警劉巖，帶你破解...
沈念sama閱讀 217,826評論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蒸健，死亡現(xiàn)場離奇詭異座享，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)纵装，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,968評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門征讲，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人橡娄，你說我怎么就攤上這事诗箍。” “怎么了挽唉？”我有些...
開封第一講書人閱讀 164,234評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵滤祖，是天一觀的道長筷狼。經(jīng)常有香客問我，道長匠童，這世上最難降的妖魔是什么埂材？我笑而不...
開封第一講書人閱讀 58,562評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮汤求，結(jié)果婚禮上俏险，老公的妹妹穿的比我還像新娘。我一直安慰自己扬绪，他們只是感情好竖独，可當(dāng)我...
茶點(diǎn)故事閱讀 67,611評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著挤牛，像睡著了一般莹痢。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上墓赴，一...
開封第一講書人閱讀 51,482評論 1贊 302
城市分裂傳說
那天竞膳，我揣著相機(jī)與錄音，去河邊找鬼诫硕。笑死坦辟，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的痘括。我是一名探鬼主播长窄，決...
沈念sama閱讀 40,271評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼纲菌！你這毒婦竟也來了挠日？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,166評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤翰舌，失蹤者是張志新（化名）和其女友劉穎嚣潜，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體椅贱，經(jīng)...
沈念sama閱讀 45,608評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡懂算，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,814評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了庇麦。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片计技。...
茶點(diǎn)故事閱讀 39,926評論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖山橄，靈堂內(nèi)的尸體忽然破棺而出垮媒，到底是詐尸還是另有隱情，我是刑警寧澤，帶...
沈念sama閱讀 35,644評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布睡雇，位于F島的核電站萌衬，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏它抱。R本人自食惡果不足惜秕豫，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,249評論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望观蓄。院中可真熱鬧混移，春花似錦、人聲如沸蜘腌。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,866評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽撮珠。三九已至，卻和暖如春金矛，著一層夾襖步出監(jiān)牢的瞬間芯急，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,991評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工驶俊，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留娶耍，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,063評論 3贊 370
代替公主和親
正文我出身青樓饼酿，卻偏偏與公主長得像榕酒，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子故俐，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,871評論 2贊 354