【題目描述】
Given a boolean 2D matrix,?0?is represented as the sea,?1?is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.
給一個(gè)01矩陣，求不同的島嶼的個(gè)數(shù)鱼响。
0代表海鸣剪，1代表島，如果兩個(gè)1相鄰丈积，那么這兩個(gè)1屬于同一個(gè)島筐骇。我們只考慮上下左右為相鄰。
【題目鏈接】
www.lintcode.com/en/problem/number-of-islands/
【題目解析】
Union Find 利用Union Find的find和union操作江滨，對(duì)島嶼進(jìn)行合并計(jì)數(shù)铛纬。因?yàn)閁nionFind結(jié)構(gòu)一般來說是一維的
| 1 | 2 | 3 | 4 |
-----------------
| 2 | 2 | 2 | 4 |
表達(dá)了如下的連通結(jié)構(gòu)
1 - 2? ? 4
| /
3
因此可以轉(zhuǎn)換二維矩陣坐標(biāo)為一維數(shù)字，M?N 的矩陣中`(i,j) -> i?N + j`唬滑。
建立UnionFind的parent[] (或者 parent hashmap)告唆，初始化各個(gè)parent[i * N + j] = i * N + j，如果grid[i][j] == true晶密，則島嶼計(jì)數(shù)count++
之后再對(duì)矩陣遍歷一次擒悬，當(dāng)遇到島嶼時(shí)，則要檢查上下左右四個(gè)方向的鄰近點(diǎn)稻艰，如果也是島嶼則合并懂牧，并且count--；
Union Find結(jié)構(gòu)可以用Path Compression和Weighted Union進(jìn)行優(yōu)化尊勿。
【參考答案】
