package leetcode
var dir = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
func numIslands(grid [][]byte) int {
m := len(grid)
if m == 0 {
return 0
}
n := len(grid[0])
if n == 0 {
return 0
}
res, visited := 0, make([][]bool, m)
for i := 0; i < m; i++ {
visited[i] = make([]bool, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' && !visited[i][j] {
searchIslands(grid, &visited, i, j)
res++
}
}
}
return res
}
func searchIslands(grid [][]byte, visited *[][]bool, x, y int) {
(*visited)[x][y] = true
for i := 0; i < 4; i++ {
nx := x + dir[i][0]
ny := y + dir[i][1]
if isInBoard(grid, nx, ny) && !(*visited)[nx][ny] && grid[nx][ny] == '1' {
searchIslands(grid, visited, nx, ny)
}
}
}
func isInBoard(board [][]byte, x, y int) bool {
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}