欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

全球变暖(18年4月蓝桥杯)

程序员文章站 2022-06-05 18:31:36
全球变暖 你有一张某海域NxN像素的照片,".“表示海洋、”#"表示陆地,如下所示: ….##….##……##.…####.…###.… 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。 由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水 ......

全球变暖

你有一张某海域nxn像素的照片,".“表示海洋、”#"表示陆地,如下所示:


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

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

例如上图中的海域未来会变成如下样子:





…#…

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

【输入格式】
第一行包含一个整数n。 (1 <= n <= 1000)
以下n行n列代表一张海域照片。

照片保证第1行、第1列、第n行、第n列的像素都是海洋。

【输出格式】
一个整数表示答案。

【输入样例】
7

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

【输出样例】
1

资源约定:
峰值内存消耗(含虚拟机) < 256m
cpu消耗 < 1000ms


 

原题使用字符串表示地图,这里我将海水和陆地换为0和1表示,这个变换的做法上大同小异,首先将整张地图修改为0,在#的位置上改为1,使用广度优先算法遍历整张地图。

变化前和变化后的地图不同,所以需要两种入队算法用于对应的地图,但因为对每个地图遍历之后队列中没有剩余元素,所以创造的队列可以重复使用,出队算法是相同的。

这里我的程序结果是一个分析版本。

全球变暖(18年4月蓝桥杯)

 

 

#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;
}