English
200. Number of Islands
Problem Statement
Given an m x n
2D binary grid grid
which represents a map of '1'
s (land) and '0'
s (water), return 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: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is'0'
or'1'
.
Solution:
go
package main
func numIslands(grid [][]byte) int {
result := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == '1' {
dfs(grid, i, j)
result++
}
}
}
return result
}
func dfs(grid [][]byte, row, col int) {
// return if it is out of bound horizontally
if row < 0 || row >= len(grid) {
return
}
// return if it is out of bound vertically
if col < 0 || col >= len(grid[row]) {
return
}
// return if it is not an island
if grid[row][col] == '0' {
return
}
// mark the current cell as visited
grid[row][col] = '0'
dfs(grid, row-1, col)
dfs(grid, row+1, col)
dfs(grid, row, col-1)
dfs(grid, row, col+1)
}
...