1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

// @Title: 岛屿数量 (Number of Islands)
// @Author: 15816537946@163.com
// @Date: 2019-11-19 15:04:41
// @Runtime: 0 ms
// @Memory: 2.8 MB
/*
 * @lc app=leetcode.cn id=200 lang=golang
 *
 * [200] 岛屿数量
 *
 * https://leetcode-cn.com/problems/number-of-islands/description/
 *
 * algorithms
 * Medium (45.46%)
 * Likes:    222
 * Dislikes: 0
 * Total Accepted:    26.5K
 * Total Submissions: 58.4K
 * Testcase Example:  '[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]'
 *
 * 给定一个由 '1'（陆地）和
 * '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
 *
 * 示例 1:
 *
 * 输入:
 * 11110
 * 11010
 * 11000
 * 00000
 *
 * 输出: 1
 *
 *
 * 示例 2:
 *
 * 输入:
 * 11000
 * 11000
 * 00100
 * 00011
 *
 * 输出: 3
 *
 *
 */
 /*
func numIslands(grid [][]byte) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])

	var dfs func(int, int)
	dfs = func(i, j int) {
		grid[i][j] = '0'

		if 0 <= i-1 && grid[i-1][j] == '1' {
			dfs(i-1, j)
		}
		if 0 <= j-1 && grid[i][j-1] == '1' {
			dfs(i, j-1)
		}
		if i+1 < n && grid[i+1][j] == '1' {
			dfs(i+1, j)
		}
		if j+1 < m && grid[i][j+1] == '1' {
			dfs(i, j+1)
		}
	}

	var ret int
	for i := range grid {
		for j := range grid[0] {
			if grid[i][j] == '1' {
				ret++
				dfs(i, j)
			}
		}
	}
	return ret
}
*/
func numIslands(grid [][]byte) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])

	var dfs func(int, int)
	dfs = func(i, j int) {
		grid[i][j] = '0'

		if i > 0 && grid[i-1][j] == '1' {
			dfs(i-1, j)
		}
		if j > 0 && grid[i][j-1] == '1' {
			dfs(i, j-1)
		}
		if i < n-1 && grid[i+1][j] == '1' {
			dfs(i+1, j)
		}
		if j < m-1 && grid[i][j+1] == '1' {
			dfs(i, j+1)
		}
	}

	var cnt int
	for i :=range grid {
		for j := range grid[0] {
			if grid[i][j] == '1' {
				cnt++
				dfs(i, j)
			}
		}
	}

	return cnt

}