全球变暖(18年4月蓝桥杯)
2019-12-28 11:54:19来源:博客园 阅读 ()
全球变暖(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; }
原文链接:https://www.cnblogs.com/hyffff/p/12110168.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:leetcode.383赎金信
- NOIP游记 Day0 2018-11-12
- 2018年湘潭大学程序设计竞赛G又见斐波那契(矩阵快速幂) 2018-09-18
- WPF全球化与本地化 2018-06-18
- 数据库文档 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash