老师的岛(并查集(YYOJ"/>
沈老师的岛(并查集(YYOJ
题目描述
沈老师天天说象山是个好地方,鹤浦更是个好地方。由于鹤浦是一个岛屿,沈老师更是有一个外号叫做“岛主”。现在“岛主”来请你帮帮忙,他想知道,他的家乡附近有多少个独立的岛屿?
给定一个由 ‘@’(陆地)和 ‘*’(水)组成的的二维网格,计算独立的岛屿的数量。一个岛被水包围,并且它是通过水平或垂直8个方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
输入
样例输入由多组测试数据组成。第一行输入两个正整数n和m分别代表网格的高和宽 ( 0 < n,m <= 100 )
接下来输入一个nm的网格,网格内只由字符 ‘@’ 和 '’ 组成,@代表陆地,*代表海洋。
输出
输出独立的岛屿的数量
样例输入
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
样例输出
0
1
2
AC代码
#include<bits/stdc++.h>
using namespace std;
int ans;
int s[100005];
char mp[105][105];
//初始化函数
void init(int x){for(int i = 0 ; i < x ; i ++)s[i] = i;
}
//查询函数
int find(int x){if(s[x] == x)return s[x];s[x] = find(s[x]);//父节点设为根节点 return s[x];//返回父节点
}
//合并函数
void merge(int a,int b){int a1 = find(a);int b1 = find(b);if(a1 != b1){s[a1] = b1;ans --;//每合并一个岛屿就减去一个}
}
int main(){int n,m;while(cin>>n>>m){ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>mp[i][j];if(mp[i][j]=='@')ans++;}}init(n*m);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i>0&&mp[i][j]=='@'&&mp[i-1][j]=='@')//判断当前位置的上方是否存在岛屿merge(i*m+j,(i-1)*m+j);if(j>0&&mp[i][j]=='@'&&mp[i][j-1]=='@')//判断当前位置的左方是否存在岛屿 merge(i*m+j,i*m+j-1);if(i>0&&j>0&&mp[i][j]=='@'&&mp[i-1][j-1]=='@')//判断当前位置的左上方是否存在岛屿 merge(i*m+j,(i-1)*m+j-1);if(i>0&&j!=m-1&&mp[i][j]=='@'&&mp[i-1][j+1]=='@')//判断当前位置的右上方是否存在岛屿 //(j!=m-1 ; j不能为右边界merge(i*m+j,(i-1)*m+j+1);}}cout<<ans<<endl;}return 0;
}
更多推荐
沈老师的岛(并查集(YYOJ
发布评论