5.5NumberofIslands - WisperDin/blog GitHub Wiki

Description

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

思路

可以发现这个问题是图的连通问题

找到 任意一个 ‘1’ land 的所有邻接的邻接，代表找到了一个 island

所以采用广度搜索，

首先从图开始遍历，遍历到一个 ‘1’ land开始，找到那个 '1' 的所有邻接的邻接，标记这个小岛全部的 '1' 坐标，并且找到的小岛数+1，往后遍历的时候跳过已经是 island的 ‘1’ ，直至遍历到末尾

实现

//找到的 ’1‘ 的状态
const (
	//邻接全部已经搜索完
	VIS   = 1
	//未知
	NOVIS = 0
	//邻接未搜索
	UNVIS = 2
)

func numIslands(grid [][]byte) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	unvisited = list.New()
	visited = make(map[string]int)

	islandNum := 0
	for x := 0; x < len(grid); x++ {
		for y := 0; y < len(grid[x]); y++ {
			p := &MyPoint{
				X: x,
				Y: y,
			}
			if visited[makeKey(p)] != VIS {
				islandNum += findIsland(grid, p)
			}

		}
	}
	return islandNum
}

var unvisited *list.List

var visited map[string]int

type MyPoint struct {
	X int
	Y int
}

func makeKey(p *MyPoint) string {
	return strings.Join([]string{strconv.Itoa(p.X), strconv.Itoa(p.Y)}, "-")
}

func findIsland(grid [][]byte, p *MyPoint) int {
	if isBeyond(grid, p) {
		return 0
	}
	if !isLand(grid, p) {
		return 0
	}
	unvisited.PushBack(p)
	count := 0
	for unvisited.Len() != 0 {
		count++

		sP := unvisited.Front().Value.(*MyPoint)

		xP := &MyPoint{
			X: sP.X + 1,
			Y: sP.Y,
		}

		yP := &MyPoint{
			X: sP.X,
			Y: sP.Y + 1,
		}

		xPs := &MyPoint{
			X: sP.X - 1,
			Y: sP.Y,
		}

		yPs := &MyPoint{
			X: sP.X,
			Y: sP.Y - 1,
		}

		if !isBeyond(grid, xP) && isLand(grid, xP) && visited[makeKey(xP)] == NOVIS {
			visited[makeKey(xP)] = UNVIS
			unvisited.PushBack(xP)
		}

		if !isBeyond(grid, yP) && isLand(grid, yP) && visited[makeKey(yP)] == NOVIS {
			visited[makeKey(yP)] = UNVIS
			unvisited.PushBack(yP)
		}

		if !isBeyond(grid, xPs) && isLand(grid, xPs) && visited[makeKey(xPs)] == NOVIS {
			visited[makeKey(xPs)] = UNVIS
			unvisited.PushBack(xPs)
		}

		if !isBeyond(grid, yPs) && isLand(grid, yPs) && visited[makeKey(yPs)] == NOVIS {
			visited[makeKey(yPs)] = UNVIS
			unvisited.PushBack(yPs)
		}
		visited[makeKey(sP)] = VIS

		unvisited.Remove(unvisited.Front())
	}

	return 1
}

func isLand(grid [][]byte, p *MyPoint) bool {
	if grid[p.X][p.Y] == '1' {
		return true
	}
	return false
}

func isBeyond(grid [][]byte, p *MyPoint) bool {
	if p.X < 0 || p.Y < 0 || p.X >= len(grid) || p.Y >= len(grid[p.X]) {
		return true
	}
	return false
}
⚠️ **GitHub.com Fallback** ⚠️