解题思路:
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 人评分
K-进制数 (C++代码)浏览:850 |
数列 (C++代码)浏览:664 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:625 |
C语言程序设计教程(第三版)课后习题5.7 (C++代码)浏览:842 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:619 |
简单的a+b (C语言代码)浏览:524 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1589 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:572 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:672 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:661 |