洛谷P8662[蓝桥杯 2018 省 AB] 全球变暖
题目描述
你有一张某海域
N
×
N
N \times N
N×N 像素的照片，. 表示海洋、 # 表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中 “上下左右” 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有
2
2
2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数
N
N
N。
(
1
≤
N
≤
1000
)
(1 \le N \le 1000)
(1≤N≤1000)。
以下
N
N
N 行
N
N
N 列代表一张海域照片。
照片保证第
1
1
1 行、第
1
1
1 列、第
N
N
N 行、第
N
N
N 列的像素都是海洋。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
7
.......
.##....
.##....
....##.
..####.
...###.
.......
样例输出 #1
1
提示
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
思路
连通块的一点小变种的题，我们可以像这样思考：淹没的岛屿数量=淹没前岛屿数量-淹没后的岛屿数量。 对于源照片，我们可以这样先计算出没淹没时的初始岛屿数量：
.......
.##....
.##....
....##.
..####.
...###.
.......
这个连通块与以前介绍的不同，我们用这样的思路，对于每一个“#”我们都用dfs搜索并且标记为“.”即海洋，每执行一次dfs，就将记录结果+1，这样就能计数了。
还是熟悉的dfs：
dfs(int x,int y){
if(边界条件or地图的该位置不是海洋）
return;
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
dfs(newx,newy);
}
}//示例伪代码
再对地图for循环，每个循环执行dfs，就能计数淹没前的岛屿数量了，但是，这样的计数是具有破坏性的，所以我们必须建立一个地图副本来保持源地图的完整性。
再算出淹没后的岛屿数量：首先，要弄明白什么样的岛屿块会被淹没，即如果“#”周围至少有一个“.”就会被淹没，我们标记可淹没的岛屿块为“*”。 这个同样可以在main函数中预处理。 预处理后，以上图为例：
.......
.**....
.**....
....**.
..**#*.
...***.
.......
同样我们可以dfs来计数“#”的联通块： ok，现在我们上代码：
#include
using namespace std;
int n;
int ans_before;//淹没前的岛屿计数
int ans_after;//淹没后的岛屿计数
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char pho[1001][1001];
char pho_copy[1001][1001];
void dfs1(int x,int y){
if(x>n||x<0||y>n||y<0||pho_copy[x][y]!='#'){
return;
}
pho_copy[x][y]='.';
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
dfs1(newx,newy);
}
}//借助地图副本深度搜索淹没前的岛屿
void dfs2(int x,int y){
if(x>n||x<0||y>n||y<0||pho[x][y]!='#'){
return;
}
pho[x][y]='.';
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
dfs2(newx,newy);
}
}//用源地图深度搜索淹没后的岛屿
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>pho[i][j];
pho_copy[i][j]=pho[i][j];
}
}//记录地图和副本地图
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(pho[i][j]=='#'&&(pho[i+1][j]=='.'||pho[i-1][j]=='.'||pho[i][j+1]=='.'||pho[i][j-1]=='.')){
pho[i][j]='*';
}
}
}//预处理可淹没的岛屿边界
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(pho_copy[i][j]=='#'){
ans_before++;
dfs1(i,j);
}
}
}//计算淹没前岛屿的数量
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(pho[i][j]=='#'){
ans_after++;
dfs2(i,j);
}
}
}//计算淹没后的岛屿数量
cout< return 0; } 结果是： 那么究竟错哪了？ 看下列数据： 9 ......... .#######. .#######. .#######. ..#.#.... .#######. .#######. .#######. ......... 在利用副本计算时结果是ans_before=1，在预处理后结果是ans_after=2！！！相减结果是-1！！！ 我们来看看预处理后的地图是什么样的： ......... .*******. .*#####*. .*#*#***. ..*.*.... .*#*#***. .*#####*. .*******. ......... 看起来很正常，预处理部分没有问题，那就是计数部分和dfs出问题了： 具体问题在哪呢？实际上，我们在进行淹没后的地图计数时，海水将原本的一个岛分成两个岛了，但是题目中视作是同一个岛，所以出现计数错误的情况。 如何避免呢？ 只需要在dfs2出将边界条件修改一下，将“*”出也纳入搜索区域中，在循环时我们只会遇到有幸存的岛屿才会启用dfs搜索，否则我们认为该区域已被淹没。 #include using namespace std; int n; int ans_before; int ans_after; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; char pho[1001][1001]; char pho_copy[1001][1001]; void dfs1(int x,int y){ if(x>n||x<0||y>n||y<0||pho_copy[x][y]!='#'){ return; } pho_copy[x][y]='.'; for(int i=0;i<4;i++){ int newx=x+dx[i]; int newy=y+dy[i]; dfs1(newx,newy); } }//借助地图副本深度搜索淹没前的岛屿 void dfs2(int x,int y){ if(x>n||x<0||y>n||y<0||pho[x][y]=='.'){//修改处 return; } pho[x][y]='.'; for(int i=0;i<4;i++){ int newx=x+dx[i]; int newy=y+dy[i]; dfs2(newx,newy); } }//用源地图深度搜索淹没后的岛屿 int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>pho[i][j]; pho_copy[i][j]=pho[i][j]; } }//记录地图和副本地图 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(pho[i][j]=='#'&&(pho[i+1][j]=='.'||pho[i-1][j]=='.'||pho[i][j+1]=='.'||pho[i][j-1]=='.')){ pho[i][j]='*'; } } }//预处理可淹没的岛屿边界 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(pho_copy[i][j]=='#'){ ans_before++; dfs1(i,j); } } }//计算淹没前岛屿的数量 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(pho[i][j]=='#'){ ans_after++; dfs2(i,j); } } }//计算淹没后的岛屿数量 cout< return 0; } 结果： 完美通过！ 精彩链接
您阅读本篇文章共花了：
发表评论