私信TA

用户名:uq_90400651307

访问量:779

签 名:

等  级
排  名 40691
经  验 317
参赛次数 0
文章发表 1
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

TA的其他文章


解题思路:

       1.首先根据并查集可以得到在地球变暖前一共有多少岛屿:事先求出一共有多少'#',之后每合并一个就减一,最后剩的个数就是岛屿数量。并且每个岛屿的祖先都是指向了一个,这是并查集的特点;

       2.遍历所有点,找到四面都不环水的'#',对其进行计数,因为每一座岛屿可能拥有不只一个这样的点,所以我们只对其祖先结点计数,防止重复;

       3.结果=原先岛屿-现存岛屿。

       (并查集就是一种模板,就看怎么利用了)

注意事项:

       1.这道题问的是消失了多少岛屿,注意问题,一开始我以为问现存多少岛屿耽误了时间。(得22分可能因为这个)

       2.想清楚一个问题,一个岛屿在地球变暖后可能分成两片,但还是原先的那一个岛屿,不能算成两个,我的处理就是思路里的2。(得四十多分可能是这个问题没想明白)。

参考代码:

#include<iostream>
using namespace std;
#include<cstring>
class UnionFind{
	private:
		int *p;
		int num;
		int count;
	public:
		UnionFind(int x,int c){
			num = x*x;
			p = new int[num];
			for(int i=0;i<num;i++){
				p[i] = i;
			}
			count = c;
		}
		int Find(int x){
			while(x!=p[x]){
				p[x] = p[p[x]];  // 压缩路径,可省去
				x = p[x];
			}
			return x;
		}
		void Union(int x,int y){
			int rootx = Find(x);
			int rooty = Find(y);
			if(rootx==rooty){
				return ;
			}else{
				p[rootx] = rooty;
				count--;
			}
		}
		int getCount(){
			return count;
		}
};
int main(){
	int n;
	cin>>n;
	char **dp = new char*[n];
	for(int i=0;i<n;i++){
		dp[i] = new char[n];
	}
	// 输入  
	int c = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>dp[i][j];
			if(dp[i][j]=='#'){
				c++;
			}
		}
	}
	// 画圈,将一个岛屿的'#'都指向一个祖先
	UnionFind f(n,c);
	for(int i=1;i<n-1;i++){
		for(int j=1;j<n-1;j++){
			if(dp[i][j]=='#'){
				if(dp[i][j+1]=='#'){
					f.Union(i*n+j,i*n+j+1);
				}
				if(dp[i+1][j]=='#'){
					f.Union(i*n+j,i*n+n+j);
				}
			}
		}
	}
	// 找圈内四面都不是水的'#'
	int *q = new int[n*n];
	memset(q,0,sizeof(int)*(n*n));
	for(int i=1;i<n-1;i++){
		for(int j=1;j<n-1;j++){
			if(dp[i][j]=='#' && dp[i-1][j]=='#' && dp[i+1][j]=='#' && dp[i][j-1]=='#' && dp[i][j+1]=='#'){
				int t = f.Find(i*n+j);  // 只给祖先计数,防止重复
				q[t] = 1; 
			}
		}
	}
	// 求结果 
	int sum = 0;
	for(int i=0;i<n*n;i++){
		sum += q[i];
	}
	cout<<f.getCount()-sum;
	return 0;
}


 

0.0分

4 人评分

  评论区