深度优先搜索DFS---全球变暖
内心OS:这道题是去年准备HD复试时,我用来练习DFS的。现在再做这道题,感触颇深,唉,时光蹉跎,物是人非啊~~
题目:
你有一张某海域NxN像素的照片,”.”表示海洋、”#”表示陆地,如下所示:
…….
.##….
.##….
….##.
..####.
…###.
…….
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
…….
…….
…….
…….
….#..
…….
…….
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1
【输入样例】
7
##...##
#..####
#...###
##.....
#......
.......
.......
【输出样例】
0
思路分析:
题意不难理解,即海平面上升前,求出岛屿个数 cnt_before,海平面上升以后,求出岛屿个数 cnt_after,计算两者之差,即被淹没的岛屿个数。
//1.求出海平面上升前的岛屿个数 cnt_before
//2.海平面上升以后,岛屿发生改变,得到一个新的海域 。
//3.求出海平面上升后的岛屿个数 cnt_after
//4.得到被淹没的岛屿个数(注意,一个岛屿的部分陆地被淹没后,可能会成为两个岛屿,导致海平面上升以后,岛屿的个数变多)
#include<iostream>
using namespace std; const int maxn = ;
char area[maxn][maxn]; //原始海域
char area_temp[maxn][maxn]; //备份 原始海域
int n,cnt_before = ,cnt_after = ; void DFS_cnt(int i, int j) { //统计岛屿个数
if(i < || j < || i>= n || j >= n || area[i][j] == '.' || area[i][j] == ',')//不能逾越海域边界,或碰到大海,或者被淹没的陆地,就返回---递归边界
return ;
area[i][j] = '.';
DFS_cnt(i,j+);//四个方向作为选择分支
DFS_cnt(i,j-);
DFS_cnt(i+,j);
DFS_cnt(i-,j);
} int main() {
cin>>n;
for(int i = ; i < n; ++i) {//初始化 海域
for(int j = ; j < n; ++j) {
cin>>area[i][j];
area_temp[i][j] = area[i][j]; //备份 海域
}
}
//求出海平面上升以前的岛屿个数 cnt_before
for(int i = ; i < n; ++i) {
for(int j = ; j < n ; ++j) {
if(area[i][j] == '#') {
DFS_cnt(i,j);
cnt_before++;
}
}
}
//海平面上升以后,岛屿发生改变,得到一个新的海域
for(int i = ; i < n; ++i) {
for(int j = ; j < n ; ++j) {
if(area_temp[i][j] == '#'&&(area_temp[i+][j]=='.'||area_temp[i-][j]=='.'||area_temp[i][j+]=='.'||area_temp[i][j-]=='.')) {
area_temp[i][j] = ','; //陆地被淹没了
}
area[i][j] = area_temp[i][j];
}
}
//求出海平面上升以后的岛屿个数 cnt_before
for(int i = ; i < n; ++i) {
for(int j = ; j < n ; ++j) {
if(area[i][j] == '#') {
DFS_cnt(i,j);
cnt_after++;
}
}
}
cout<<(cnt_before > cnt_after?cnt_before - cnt_after : );//被淹没的岛屿个数。
return ;
}
运行结果 1:
运行结果 2:
最新文章
- WinSetupFromUSB - 制作多系统U盘安装All-In-One的利器
- ORA-00054: resource busy and acquire with NOWAIT specified
- 《TCP/IP 详解 卷一》读书笔记-----Ping&;Traceroute
- PE文件格式图示
- Nmap 網路診斷工具基本使用技巧與教學
- ORALCE 游标简单的实例
- Python自然语言工具包(NLTK)入门
- 菜鸟学习Spring——初识Spring
- URAL1291. Gear-wheels
- geotools导出shapefile出错: java.io.IOException: Current fid index is null, next must be called before write()
- 删除已分配IP的静态IP地址池
- C#与C++、Java之比较概览
- hdu-2814-Interesting Fibonacci-斐波那契周期节
- 陈年佳酿之 - Winform ListView 控件 double click 事件中获取选中的row与column
- STL之queue
- 用Vue.js开发微信小程序:开源框架mpvue解析
- Java设计模式之《适配器模式》及应用场景
- java----JSTL学习笔记(转)
- 理解Java注解类型
- SAP Tax Service可以取代TAXBRA / RVABRA吗?(翻译) 跨国贸易云税务解决方案