内容简介：该题基本上就是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
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
王道程序员求职宝典
电子工业出版社 / 2013-11 / 56.00元
本书精选了大量知名企业的程序员笔试、面试题，重点突出、解答翔实。全书共分为四部分，各部分如下：第一部分是程序设计基础及数据结构基础，讨论C/C++基础知识以及数据结构基础知识；第二部分是计算机网络基础，讨论网络模型、套接字编程基本操作、IPv4与IPv6、子网划分、网络常用测试工具等；第三部分是操作系统基础，讨论进程与线程的基本知识、进程间通信与进程同步、内存管理的相关知识等；第四部分是其他计算机......一起来看看 《王道程序员求职宝典》 这本书的介绍吧!
