[LeetCode] 695. Max Area of Island

本文主要是介绍[LeetCode] 695. Max Area of Island，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/max-area-of-island/description/

题目

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.

思路

题目大意

矩阵 grid 相当于 一张地图，其中，1为岸，0为水面。求最大岸的面积。

解题思路

遍历整张图，当当前位置 为 1时， 对其上下左右进行 深度遍历。每探索到 位置元素为 1 时，将当前 岸面积加1，并将 当前位置 置为 0。

code

Your runtime beats 38.54 % of python3 submissions.

class Solution:def dfsFindMaxArea(self, ix, iy, grid):self.tmpLand += 1grid[ix][iy] = 0for dx in [-1 ,0, 1]:if ix + dx >= 0 and ix + dx < len(grid) and grid[ix + dx][iy ] == 1:self.dfsFindMaxArea(ix + dx, iy , grid)for dy in [-1,0, 1]:if iy + dy >= 0 and iy + dy < len(grid[ix]) and grid[ix ][iy + dy] == 1:self.dfsFindMaxArea(ix , iy + dy, grid)def maxAreaOfIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""maxland = 0for i in range(len(grid)):for j in range(len(grid[i])):self.tmpLand = 0if grid[i][j] == 1:self.dfsFindMaxArea(i, j, grid)if self.tmpLand > maxland:maxland = self.tmpLandreturn maxland

这篇关于[LeetCode] 695. Max Area of Island的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---