package Graph
// 时间复杂度: O(n * m), 空间复杂度: O(n * m)
func numIslands(grid [][]byte) int {
n, m := len(grid), len(grid[0])
islands := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == '1' {
islands++
infect(grid, i, j)
}
}
}
return islands
}
func infect(grid [][]byte, i, j int) {
if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
return
}
grid[i][j] = '2'
infect(grid, i-1, j)
infect(grid, i+1, j)
infect(grid, i, j-1)
infect(grid, i, j+1)
}