LeetCode | 0695. Max Area of Island【Python】

清疚 2023-07-09 13:23 2阅读 0赞

> LeetCode 0695. Max Area of Island【Medium】【Python】【DFS】

### Problem ###

[LeetCode][]

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.

### 问题 ###

[力扣][Link 1]

给定一个包含了一些 0 和 1的非空二维数组 `grid` , 一个 岛屿 是由四个方向 (水平或垂直) 的 `1` (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

**示例 1:**

对于上面这个给定矩阵应返回 `6`。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

**示例 2:**

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

对于上面这个给定的矩阵, 返回 `0`。

**注意:** 给定的矩阵`grid` 的长度和宽度都不超过 50。

### 思路 ###

**DFS**

把走过的路都设为 0，找到岛屿的最大面积。

**时间复杂度:** O(m\*n)  
**空间复杂度:** O(m\*n)

##### Python3代码 #####

class Solution:
        def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
            self.ans = 0
            self.island = 0
            m, n = len(grid), len(grid[0])
            for i in range(m):
                for j in range(n):
                    if grid[i][j]:  # 1: island
                        self.dfs(grid, i, j)
                        self.ans = max(self.ans, self.island)
                        self.island = 0
            return self.ans
        
        # dfs template
        def dfs(self, grid, i, j):
            m, n = len(grid), len(grid[0])
            grid[i][j] = 0
            self.island += 1
            directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
            for direction in directions:
                x, y = i + direction[0], j + direction[1]
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    self.dfs(grid, x, y)

### 代码地址 ###

[GitHub链接][GitHub]

[LeetCode]: https://leetcode.com/problems/max-area-of-island/
[Link 1]: https://leetcode-cn.com/problems/max-area-of-island/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0695-Max-Area-of-Island/0695.py