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

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

内容简介：该题基本上就是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
}

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

查看所有标签

猜你喜欢:

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

码农书籍

宇宙涟漪中的孩子

谢云宁 / 四川科学技术出版社 / 2017-11 / 28.00元

近未来。日冕科技公司通过建造围绕太阳的光幕搜集了近乎无穷的能源，这些能源主要用于地球上的网络空间建设。随着全球网络时间频率的不断提升，越来越多的人选择接驳进虚拟空间，体验现实中难以经历的丰富人生。网络互动小说作者宁天穹一直自认为是这些人中普通的一员，有一天却被一名读者带进反抗组织，了解到日冕公司的各种秘密，并被告知自己的小说将在抵抗运动中起到重要作用。起初他拒绝参与，但看到地球被笼......一起来看看《宇宙涟漪中的孩子》这本书的介绍吧!

码农工具