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

栏目: 编程工具 · 发布时间: 5年前

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

Max Area of Island

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

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

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

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

深度优先搜索

思路

该题基本上就是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
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

The Big Red Fez

Seth Godin / Free Press / 2002-01-15 / USD 11.00

YOUR WEB SITE IS COSTING YOU MONEY. IT'S ALSO FILLED WITH SIMPLE MISTAKES THAT TURN OFF VISITORS BEFORE THEY HAVE A CHANCE TO BECOME CUSTOMERS. According to marketing guru Seth Godin, a web s......一起来看看《The Big Red Fez》这本书的介绍吧!

码农工具