全球變暖（18年4月藍橋杯）

全球變暖

你有一張某海域NxN像素的照片，".“表示海洋、”#"表示陸地，如下所示：

…
.##…
.##…
…##.
…####.
…###.
…

其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼，例如上圖就有2座島嶼，

由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒，具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒，

例如上圖中的海域未來會變成如下樣子：

…
…
…
…
…#…
…
…

請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒，

【輸入格式】
第一行包含一個整數N， (1 <= N <= 1000)
以下N行N列代表一張海域照片，

照片保證第1行、第1列、第N行、第N列的像素都是海洋，

【輸出格式】
一個整數表示答案，

【輸入樣例】
7
…
.##…
.##…
…##.
…####.
…###.
…

【輸出樣例】
1

資源約定：
峰值記憶體消耗（含虛擬機） < 256M
CPU消耗 < 1000ms

原題使用字串表示地圖，這里我將海水和陸地換為0和1表示，這個變換的做法上大同小異，首先將整張地圖修改為0，在#的位置上改為1，使用廣度優先演算法遍歷整張地圖，

變化前和變化后的地圖不同，所以需要兩種入隊演算法用于對應的地圖，但因為對每個地圖遍歷之后佇列中沒有剩余元素，所以創造的佇列可以重復使用，出隊演算法是相同的，

這里我的程式結果是一個分析版本，

#include<bits/stdc++.h>
using namespace std;
int m,n,counta=0,countb=0;
int qwe[500][500];//變化前地圖
int qwr[500][500];//變化后地圖
int visited[500][500];
struct queue{
    int x[500];
    int y[500];
    int head,tail;
}qqq;
int enqueue(int o,int p){
    if((qqq.tail+1)%500==qqq.head){
        return 0;
    }
    if(o<0||o>=m||p<0||p>=n){
        return 0;
    }
    if(visited[o][p]!=0||qwe[o][p]==0){
        return 0;
    }
    qqq.x[qqq.tail]=o;
    qqq.y[qqq.tail]=p;
    qqq.tail++;
    return 1;
}
int enqueue1(int o,int p){
    if((qqq.tail+1)%500==qqq.head){
        return 0;
    }
    if(o<0||o>=m||p<0||p>=n){
        return 0;
    }
    if(visited[o][p]!=0||qwr[o][p]==0){
        return 0;
    }
    qqq.x[qqq.tail]=o;
    qqq.y[qqq.tail]=p;
    qqq.tail++;
    return 1;
}
int dequeue(){
    if(qqq.head==qqq.tail){
        return 0;
    }
    qqq.head++;
    return 1;
}
int check(int o,int p){
    if(o<0||o>=m||p<0||p>=n){
        return 2;
    }
    if(qwe[o][p]==1){
        return 1;
    }
    return 0;
}
bool isempty(){
    if(qqq.head==qqq.tail){
        return true;
    }
    return false;
}
int main(){
    qqq.head=0;
    qqq.tail=0;
    int f,g;
    int i,j;
    cin>>m;
    cin>>n;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            cin>>qwe[i][j];
            visited[i][j]=0;
        }
    }
    for(i=0;i<500;i++){
        for(j=0;j<500;j++){
            if(qwe[i][j]==1&&visited[i][j]==0){
            enqueue(i,j);
            while (!isempty()){
                f=qqq.x[qqq.head];
                g=qqq.y[qqq.head];
                visited[f][g]=counta+1;
                dequeue();
                enqueue(f-1,g);
                enqueue(f+1,g);
                enqueue(f,g+1);                
                enqueue(f,g-1);
            }
            counta++;
        }
    }    
}
    cout<<"--------------------"<<endl;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            cout<<visited[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"tail"<<qqq.tail<<"  head"<<qqq.head<<endl;
    cout<<"count"<<counta<<endl;
    cout<<"--------------------"<<endl;
for(i=0;i<m;i++){
    for(j=0;j<n;j++){
        if(check(i,j)==1){
            if(check(i-1,j)*check(i+1,j)*check(i,j-1)*check(i,j+1)!=0){
                qwr[i][j]=1;
            }
        }else{
            qwr[i][j]=0;
        }
        cout<<qwr[i][j]<<" ";
        visited[i][j]=0;
    }
    cout<<endl;
}
    for(i=0;i<500;i++){
        for(j=0;j<500;j++){
            if(qwr[i][j]==1&&visited[i][j]==0){
            enqueue(i,j);
            while (!isempty()){
                f=qqq.x[qqq.head];
                g=qqq.y[qqq.head];
                visited[f][g]=countb+1;
                dequeue();
                enqueue1(f-1,g);
                enqueue1(f+1,g);
                enqueue1(f,g+1);                
                enqueue1(f,g-1);
            }
            countb++;
        }
    }    
}
    cout<<"--------------------"<<endl;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            cout<<visited[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"tail"<<qqq.tail<<"  head"<<qqq.head<<endl;
    cout<<"count"<<countb<<endl;
}

標籤：C++

上一篇：快速入門Flink(5)——Flink中的17種TransFormAction算子（面試必問，建議收藏）

下一篇：五年C語言程式員，是深耕技識訓是走管理？