Force buckle topic link cow guest topic link

There are two ideas

  • Depth First Search (DFS)
  • Breadth first search (breadth first search, referred to as BFS), also known as width first search

Method a

Depth-first search is stack based.

We named the structure type Earth because naming it Node or Point might conflict with the internal common type name of the site.

Note that the I and J in Earth are type-optimized for the number of rows and columns in the matrix, without using int. Uint8 can be used if the number of rows and columns is less than 200. Uint16 can be used if the number of rows and columns is within 300 (force <=300).

import "container/list"

func numIslands(grid [][]byte) int {
    var c int // Count the number of islands
    for i, row := range grid {
        for j, n := range row {
            if n == '1' {
                c++ // Increments DFS by 1 each time
                dfs(grid, i, j)
            }
        }
    }
    return c
}

type Earth struct {
    I uint16 // row
    J uint16 // col
}

Depth-first search
// Every time DFS is called, the connected '1' around the grid[I][j] is found
func dfs(grid [][]byte, i, j int) {
    rows := uint16(len(grid))
    cols := uint16(len(grid[0]))
    sk := NewStack()
    sk.Push(Earth{I:uint16(i), J:uint16(j)})
    grid[i][j] = '0' // Set '0' to record that the grid has been visited
    for! sk.IsEmpty() { p := sk.Peek().(Earth) sk.Pop()// right
        if p.J+1 < cols && grid[p.I][p.J+1] = ='1' { // If not, join the search set
            sk.Push(Earth{I:uint16(p.I), J:uint16(p.J+1)})
            grid[p.I][p.J+1] = '0'
        }
        // left
        if p.J >= 1 && grid[p.I][p.J- 1] = ='1' {
            sk.Push(Earth{I:uint16(p.I), J:uint16(p.J- 1)})
            grid[p.I][p.J- 1] = '0'
        }
        // up
        if p.I >= 1 && grid[p.I- 1][p.J] == '1' {
            sk.Push(Earth{I:uint16(p.I)- 1, J:uint16(p.J)})
            grid[p.I- 1][p.J] = '0'
        }
        // down
        if p.I+1 < rows && grid[p.I+1][p.J] == '1' {
            sk.Push(Earth{I:uint16(p.I)+1, J:uint16(p.J)})
            grid[p.I+1][p.J] = '0'}}}/ / stack implementation
type Stack struct {
	l *list.List
}

func NewStack(a) *Stack {
	return &Stack{
		l: list.New(),
	}
}

func (o *Stack) Push(v interface{}) {
	o.l.PushBack(v)
}

func (o *Stack) Peek(a) interface{} {
	if o.IsEmpty() {
		panic("Stack is empty")}return o.l.Back().Value
}

func (o *Stack) Pop(a) {
	if o.IsEmpty() {
		panic("Stack is empty")
	}
	o.l.Remove(o.l.Back())
}

func (o *Stack) IsEmpty(a) bool {
	return o.l.Len() == 0
}

func (o *Stack) Len(a) int {
	return o.l.Len()
}
Copy the code

Method 2

Breadth-first search is based on queues.

func numIslands(grid [][]byte) int {
    var c int // Count the number of islands
    for i, row := range grid {
        for j, n := range row {
            if n == '1' {
                c++ // Add 1 for each search
                bfs(grid, i, j)
            }
        }
    }
    return c
}

type Earth struct {
    I uint16 // row
    J uint16 // col
}

// breadth-first search
// Every time we call BFS, we find the connected '1' around the grid[I][j]
func bfs(grid [][]byte, i, j int) {
    rows := uint16(len(grid))
    cols := uint16(len(grid[0]))
    q := NewQueue()
    q.Push(Earth{I:uint16(i), J:uint16(j)})
    grid[i][j] = '0' // Mark the grid as visited
    for! q.IsEmpty() { p := q.Pop().(Earth)// right
        if p.J+1 < cols && grid[p.I][p.J+1] = ='1' { // If not, join the search set
            q.Push(Earth{I:uint16(p.I), J:uint16(p.J+1)})
            grid[p.I][p.J+1] = '0'
        }
        // left
        if p.J >= 1 && grid[p.I][p.J- 1] = ='1' {
            q.Push(Earth{I:uint16(p.I), J:uint16(p.J- 1)})
            grid[p.I][p.J- 1] = '0'
        }
        // up
        if p.I >= 1 && grid[p.I- 1][p.J] == '1' {
            q.Push(Earth{I:uint16(p.I- 1), J:uint16(p.J)})
            grid[p.I- 1][p.J] = '0'
        }
        // down
        if p.I+1 < rows && grid[p.I+1][p.J] == '1' {
            q.Push(Earth{I:uint16(p.I+1), J:uint16(p.J)})
            grid[p.I+1][p.J] = '0'}}}// Queue implementation
type Queue struct {
	l *list.List
}

func NewQueue(a) *Queue {
	return &Queue{
		l: list.New(),
	}
}

func (o *Queue) Push(v interface{}) {
	o.l.PushBack(v)
}

func (o *Queue) Pop(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")
	}
	e := o.l.Front()
	o.l.Remove(e)
	return e.Value
}

func (o *Queue) Front(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")}return o.l.Front().Value
}

func (o *Queue) Back(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")}return o.l.Back().Value
}

func (o *Queue) IsEmpty(a) bool {
	return o.l.Len() == 0
}

func (o *Queue) Len(a) int {
	return o.l.Len()
}
Copy the code