中矿新生赛 H 璐神看岛屿【BFS/DFS求联通块/连通块区域在边界则此连通块无效】...

 2023-09-05 阅读 607 评论 0

摘要:时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld 题目描述 璐神现在有张n*m大小的地图,地图上标明了陆地(用"#"表示)和海洋(用"."表示&
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

璐神现在有张n*m大小的地图,地图上标明了陆地(用"#"表示)和海洋(用"."表示),现在璐神要计算这张地图上岛屿的数量。
已知岛屿是由陆地的连通块组成,即一块陆地的上、下、左、右,左上,右上,左下,右下有其他陆地,则构成连通块,以此类推。
此外,岛屿的详细定义如下:
1、岛屿的周围必须全是海洋。
2、如果连通块有任意区域在地图边界,则该连通块不是岛屿。

输入描述:

第1行输入两个整数n,m,代表地图的长和宽。
第2-n+1行,每行输入m个字符,字符为"#"表示陆地,为"."表示海洋。
数据保证:0<n,m≤200

输出描述:

输出一行整数,代表岛屿的数量。
示例1

输入

3 3
...
.#.
...

输出

1

说明

只有中间的1块陆地是岛屿,所以岛屿数=1
示例2

输入

3 3
#..
.#.
...

输出

0

说明

中间的连通块有区域在边界,所以不是岛屿,岛屿数=0。

【分析】:bfs 求解连通块,注意的是在求解过程中,如果出现连通块区域在边界,则记录此连通块无效,但仍需将 bfs 操作进行完。
【代码】:
#include <bits/stdc++.h>using namespace std;
const int maxn = 250;
char mp[250][250];
int vis[maxn][maxn]={0};
int dir[][2] ={{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
int n,m,flag=0;void dfs(int x,int y)
{vis[x][y]=1;if(x==0||y==0||x==n-1||y==m-1)flag=1;for(int i=0;i<8;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(mp[tx][ty]=='#'&&tx>=0&&ty>=0){mp[tx][ty]='.';dfs(tx,ty);}}
}
int main()
{int sum=0;cin>>n>>m;for(int i=0;i<n;i++)cin>>mp[i];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mp[i][j]=='#'){flag=0;dfs(i,j);if(flag==0)sum++;}}}cout<<sum<<endl;return 0;
}
DFS

 

#include<bits/stdc++.h>
using namespace std;const int maxn=210;char mp[maxn][maxn];
int vis[maxn][maxn];
const int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};int n,m,ans=0;void bfs(int x,int y){if(mp[x][y]=='.'){vis[x][y]=2;return;}if(x==0||y==0||x==n-1||y==m-1){vis[x][y]=2;//  return;
    }queue<pair<int,int> >q;q.push(make_pair(x,y));while(!q.empty()){int nowx=q.front().first;int nowy=q.front().second;if(nowx==0||nowy==0||nowx==n-1||nowy==m-1){vis[x][y]=2;//return;
        }q.pop();for(int i=0;i<8;++i){int x1=nowx+dir[i][0];int y1=nowy+dir[i][1];if(vis[x1][y1]==0&&mp[x1][y1]=='#'){vis[x1][y1]=1;q.push(make_pair(x1,y1));}}}
}int main(){while(cin>>n>>m){memset(mp,0,sizeof(mp));memset(vis,false,sizeof(vis));ans=0;for(int i=0;i<n;++i)cin>>mp[i];for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(!vis[i][j]){vis[i][j]=1;bfs(i,j);if(vis[i][j]==1){ans++;}}}}cout<<ans<<endl;}return 0;
}
BFS

 

转载于:https://www.cnblogs.com/Roni-i/p/7909104.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/140.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息