给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。
并查集。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := [][]byte{
{49, 49, 49, 49, 48},
{49, 49, 48, 49, 48},
{49, 49, 48, 49, 48},
{49, 49, 48, 48, 48},
{48, 48, 48, 48, 48}}
ret := numIslands(arr)
fmt.Println(ret)
}
func numIslands(board [][]byte) int {
row := len(board)
col := len(board[0])
uf := NewUnionFind(board)
for j := 1; j < col; j++ {
if board[0][j-1] == '1' && board[0][j] == '1' {
uf.union(0, j-1, 0, j)
}
}
for i := 1; i < row; i++ {
if board[i-1][0] == '1' && board[i][0] == '1' {
uf.union(i-1, 0, i, 0)
}
}
for i := 1; i < row; i++ {
for j := 1; j < col; j++ {
if board[i][j] == '1' {
if board[i][j-1] == '1' {
uf.union(i, j-1, i, j)
}
if board[i-1][j] == '1' {
uf.union(i-1, j, i, j)
}
}
}
}
return uf.getSets()
}
type UnionFind2 struct {
parent []int
size []int
help []int
col int
sets int
}
func NewUnionFind(board [][]byte) *UnionFind2 {
ret := &UnionFind2{}
ret.col = len(board[0])
ret.sets = 0
row := len(board)
length := row * ret.col
ret.parent = make([]int, length)
ret.size = make([]int, length)
ret.help = make([]int, length)
for r := 0; r < row; r++ {
for c := 0; c < ret.col; c++ {
if board[r][c] == '1' {
i := ret.index(r, c)
ret.parent[i] = i
ret.size[i] = 1
ret.sets++
}
}
}
return ret
}
// (r,c) -> i
func (this *UnionFind2) index(r int, c int) int {
return r*this.col + c
}
// 原始位置 -> 下标
func (this *UnionFind2) find(i int) int {
hi := 0
for i != this.parent[i] {
this.help[hi] = i
hi++
i = this.parent[i]
}
for hi--; hi >= 0; hi-- {
this.parent[this.help[hi]] = i
}
return i
}
func (this *UnionFind2) union(r1 int, c1 int, r2 int, c2 int) {
i1 := this.index(r1, c1)
i2 := this.index(r2, c2)
f1 := this.find(i1)
f2 := this.find(i2)
if f1 != f2 {
if this.size[f1] >= this.size[f2] {
this.size[f1] += this.size[f2]
this.parent[f2] = f1
} else {
this.size[f2] += this.size[f1]
this.parent[f1] = f2
}
this.sets--
}
}
func (this *UnionFind2) getSets() int {
return this.sets
}执行结果如下：
