2021-04-18: given a two-dimensional array matrix, the value in it is either 1 or 0,

2021-04-18： Given a two-dimensional array matrix, The value in it is not 1 Namely 0, On 、 Next 、 Left 、 Right adjacent 1 Think it's an island , return matrix The number of Nakajima .

Fuda answer 2021-04-18：

Union checking set .

The code to use golang To write . The code is as follows ：

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
}

//  Original location  ->  Subscript 
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
}

The results are as follows ：

Insert picture description here

---

Zuo Shen java Code

Power button 200. Number of Islands