题解 | #岛屿数量#

package main

import "container/list"

/*
*
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
(注：存储的01数据其实是字符'0','1')
*/
func solve(grid [][]byte) int {
	n := len(grid)
	if n <= 0 {
		return 0
	}
	m := len(grid[0])
	vis := make([][]bool, n)
	for i := 0; i < n; i++ {
		vis[i] = make([]bool, m)
	}
	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if vis[i][j] || grid[i][j] != '1' {
				continue
			}
			ans++
			solve109(grid, vis, list.New(), i, j)
		}
	}
	return ans
}

func solve109(grid [][]byte, vis [][]bool, que *list.List, stX int, stY int) {
	dx := []int{0, 0, 1, -1}
	dy := []int{1, -1, 0, 0}
	n := len(grid)
	m := len(grid[0])
	type Node struct {
		x int
		y int
	}
	que.PushBack(&Node{x: stX, y: stY})
	vis[stX][stY] = true
	for que.Len() > 0 {
		e := que.Front()
		que.Remove(e)
		node := e.Value.(*Node)
		for i := 0; i < 4; i++ {
			nx := node.x + dx[i]
			ny := node.y + dy[i]
			if nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || grid[nx][ny] != '1'  {
				continue
			}
			vis[nx][ny] = true
			que.PushBack(&Node{x: nx, y: ny})
		}
	}
}