[Leetcode] Max Area of Island 最大岛屿面积

Max Area of Island

最新更新请见： https://yanjia.me/zh/2019/02/...

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

[[0,0,0,0,0,0,0,0]]

深度优先搜索

思路

该题基本上就是Number of Islands的变形题，唯一的区别是在Number of Islands中我们只需要将搜索到的陆地置为0，保证其不会再被下次探索所用就行了。但这题多了一要求就是要同时返回岛屿的面积。那么最简单的方式就是在递归的时候，每个搜索到的格子都将自身的面积1，加上四个方向搜索出来的延伸面积都加上，再返回给调用递归的那个格子作为延伸面积使用，这样一直返回到岛屿的起始格子时，面积之和就是岛屿的总面积了。

代码

Go

func maxAreaOfIsland(grid [][]int) int {
    maxArea := 0
    for i := range grid {
        for j := range grid[i] {
            area := measureIsland(grid, i, j)
            if area > maxArea {
                maxArea = area
            }
        }
    }
    return maxArea
}

func measureIsland(grid [][]int, x, y int) int {
    if grid[x][y] == 0 {
        return 0
    }
    area := 1
    grid[x][y] = 0
    if x > 0 {
        area += measureIsland(grid, x-1, y)
    }
    if x < len(grid)-1 {
        area += measureIsland(grid, x+1, y)
    }
    if y > 0 {
        area += measureIsland(grid, x, y-1)
    }
    if y < len(grid[0])-1 {
        area += measureIsland(grid, x, y+1)
    }
    return area
}