Table of Contents
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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Golang Solution
- Refer to earlier problem of Rotten Oranges and use the same code.
- Modify slightly to achieve solution for this problem
//Practice number of island
package main
import (
"fmt"
)
func bfs(grid [][]byte, row, col int) {
maxRow := len(grid)
maxCol := len(grid[0])
q := [][2]int{}
grid[row][col] = '0'
q = append(q, [2]int{row, col})
for len(q) > 0 {
// deque
current := q[0]
q = q[1:]
// Iterate over neighbours
nc := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for _, direction := range nc {
newRow := current[0] + direction[0]
newCol := current[1] + direction[1]
// check boundaries
if newRow >= 0 && newRow < maxRow && newCol >= 0 && newCol < maxCol && grid[newRow][newCol] == '1' {
// enque
q = append(q, [2]int{newRow, newCol})
grid[newRow][newCol] = '0'
}
}
}
}
func numIslands(grid [][]byte) int {
numberOfIslands := 0
for row, entries := range grid {
for col, value := range entries {
if value == '1' {
bfs(grid, row, col)
numberOfIslands++
}
}
}
return numberOfIslands
}
func main() {
grid := [][]byte{
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'},
}
fmt.Printf("numIslands=%d\n", numIslands(grid))
}
Output
numIslands=1
Program exited.
Visit https: https://codeandalgo.com for more such content.
Leave a Reply