未分類

Number of Islands

BreadthFirstSearch, DepthFirstSearch, Go, LeetCode, UnionFind

Number of Islands

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:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

Default:

1
2
3
func numIslands(grid [][]byte) int {
}

解答思路:

要找出共有幾座島嶼在地圖上，最簡單的方式就是先遍歷整個二元陣列，如果碰到島嶼的任一點陸地(值為1)就在計數器上+1，並以該點開始往上下左右延伸將整個島嶼移除就可以避免重覆計算，直到完全遍歷完整個二元陣列也表示將所有島嶼從地圖上移除，最後計數器的島嶼數就是我們要的答案。

程式碼解說:

一開始便以巢狀迴圈來遍歷整個二元陣列，如果碰到島嶼的任一點陸地就在計數器上+1，並將整個二元陣列及該點座標帶入遞回函數以移除整座島嶼，直到完全遍歷完整個二元陣列便向上回傳計數器的結果

1
2
3
4
5
6
7
8
9
10
11
12
func numIslands(grid [][]byte) int {
	var count int
	for i, g := range grid {
		for j, v := range g {
			if string(v) == "1" {
				count++
				removeIsland(grid, i, j)
			}
		}
	}
	return count
}

接著就是處理遞回函數的細節，如果座標位於地圖的範圍內且該點位置為陸地的話，便先將該點的陸地移除(1改為0)，之後以該座標為中心分別向上下左右鄰近的位置做遞回直到完全移除整座島嶼為止

1
2
3
4
5
6
7
8
9
func removeIsland(grid [][]byte, i int, j int) {
	if i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0]) && grid[i][j] == '1' {
		grid[i][j] = '0'
		removeIsland(grid, i+1, j)
		removeIsland(grid, i, j+1)
		removeIsland(grid, i-1, j)
		removeIsland(grid, i, j-1)
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func numIslands(grid [][]byte) int {
	var count int
	for i, g := range grid {
		for j, v := range g {
			if string(v) == "1" {
				count++
				removeIsland(grid, i, j)
			}
		}
	}
	return count
}
func removeIsland(grid [][]byte, i int, j int) {
	if i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0]) && grid[i][j] == '1' {
		grid[i][j] = '0'
		removeIsland(grid, i+1, j)
		removeIsland(grid, i, j+1)
		removeIsland(grid, i-1, j)
		removeIsland(grid, i, j-1)
	}
}

總結:

給一二元陣列包含0(海水)與1(陸地)，要找出共有幾座島嶼在地圖上，最簡單的方式就是先遍歷整個二元陣列，如果碰到島嶼的任一點陸地就在計數器上+1，並以該點開始往上下左右延伸將整個島嶼移除就可以避免重覆計算，直到完全遍歷完整個二元陣列也表示將所有島嶼從地圖上移除，最後計數器的島嶼數就是我們要的答案。

分享到