Leetcode - number-of-islands

Given a 2d grid map of '1's (land) and '0's (water), count 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:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Use a walk method to do recursion in the grid. Once the grid is '1', islands count +1, and then mark it as '2' and then go as up, down, left, right directions. If i, j are in the edge, return 0.

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    
    result := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            result += walk(grid, i, j)
        }
    }

    return result
}

func walk(grid [][]byte, i, j int) int {
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return 0
    }
    
    if grid[i][j] == '1' {
        grid[i][j] = '2'
        walk(grid, i+1, j)
        walk(grid, i-1, j)
        walk(grid, i, j-1)
        walk(grid, i, j+1)
        return 1
    }
    return 0
}

# @param {Character[][]} grid
# @return {Integer}
def num_islands(grid)
    return 0 if grid.length == 0 || grid[0].length == 0
    count = 0
    for i in 0..grid.length-1
        for j in 0..grid[i].length-1
            count += walk(grid, i, j)
        end
    end
    
    return count
end

def walk(grid, i, j)
    if i < 0 || j < 0 || i >= grid.length || j >= grid[0].length
        return 0
    end
    while grid[i][j] == '1'
        grid[i][j] = '2'
        walk(grid, i, j+1)
        walk(grid, i, j-1)
        walk(grid, i+1, j)
        walk(grid, i-1, j)
        return 1
    end
    return 0
end

• 相关文章
• 全局相关文章