hiho一下第183周《Counting Islands II》题目分析

0
0

《Counting Islands II》题目分析

本题是一道非常经典的并查集题目。

首先我们来分析一下,每周新添加的陆地会对岛屿数目有什么影响。

我们用X表示新添加的陆地,X上下左右四个位置分别用1234来表示:

.1.
3X4
.2.

1) X周围没有岛屿:

...
.X.
...

这时新添加的X会导致岛屿数目+1

2) X周围有一座岛屿:

.#.    .##
.X.    .X# (1和4属于同一座岛屿)
...    ...

这时新添加的X会与#的岛屿合并,岛屿数目不变

3) 同理,如果X周围有二、三、四座岛屿,那么新添加的X会把这些岛屿都合并成一座岛屿。岛屿数目-1, -2, -3。

.#.
#X#
.#.

通过上面的分析,我们发现解决这道题目需要一种数据结构或算法可以用比较低的复杂度快速实现:

1) 查询一块陆地属于哪个岛屿
2) 合并两个岛屿

如果我们把一块陆地看作一个元素,一个岛屿看作一个集合。那么并查集就是解决以上两个问题的利器。

关于并查集可以参考#1066题或者网上的资料,这里不再赘述。

5 answer(s)

0

没搞懂,大伙知道怎么写么?

0

用DFS就会超时吗

0

就是合并合并啊。不过注意合并的时候需要保证所以指向被合并集合的点都需要更新一下。 然后就是合并的时候可以小集合合并到大集合

0

include

include

include

define maxn 10000

define INF 0x3f3f3f3f

using namespace std;

char arc[maxn][maxn]; int pre[maxn*maxn]; int mlen,nlen;

int find(int v) { if(pre[v]==v) return v; else{ pre[v]=find(pre[v]); return pre[v]; } }

void merge(int v,int u) { int t1=find(v),t2=find(u); if(t1!=t2) if(t1

void merge_4_dir(int x,int y) { int tt=x*nlen+y; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; for(int i=0; i<4; i++){ int tx=x+dx[i]; int ty=y+dy[i]; int uu=tx*nlen+ty; if(tx>=0&&tx=0&&ty

int main() { //输入地图的高和长 while(cin>>mlen>>nlen) { for(int i=0;i>arc[i]; int cx,cy; for(int x=0;x

0

我喜欢你!jfj

write answer 切换为英文 切换为中文


转发分享