LeetCode: 695 Max Area of Island

You are given an m x n binary matrix grid representing a map of ‘1’s (land) and ‘0’s (water). An island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example:

Input: grid = [
  [0,0,1,0,0],
  [0,1,1,1,0],
  [0,0,0,0,0],
  [1,1,0,0,1],
  [1,1,0,1,1]
]
Output: 6

Explanation:

The largest island has an area of 6.

问题

给定一个 m x n 的二进制矩阵 grid，它表示一个由 ‘1’（陆地）和 ‘0’（水）组成的地图。岛屿是一组通过4个方向（水平或垂直）连接在一起的 1（表示陆地）。你可以假设网格的四个边缘都被水包围。

岛屿的面积是岛屿中值为 1 的单元格的数量。

返回 grid 中岛屿的最大面积。如果没有岛屿，则返回 0。

解决方案

深度优先搜索 (DFS) 和广度优先搜索 (BFS)

Approach 1: Depth-First Search (DFS) / 深度优先搜索 (DFS)

This approach uses DFS to explore each island fully and calculate its area. Starting from any ‘1’ that hasn’t been visited, we recursively explore all connected ‘1’s (land) and count the number of cells to determine the area of the island. We keep track of the maximum area found during the traversal.

这种方法使用 DFS 完全探索每个岛屿并计算其面积。从任何尚未访问的 ‘1’ 开始，我们递归地探索所有连接的 ‘1’（陆地）并计算单元格的数量，以确定岛屿的面积。在遍历过程中，我们跟踪找到的最大面积。

Implementation / 实现

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(r, c):
            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0:
                return 0
            grid[r][c] = 0  # Mark as visited
            area = 1
            area += dfs(r - 1, c)
            area += dfs(r + 1, c)
            area += dfs(r, c - 1)
            area += dfs(r, c + 1)
            return area

        max_area = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    max_area = max(max_area, dfs(r, c))

        return max_area

Explanation / 解释

DFS Function / DFS 函数
```
def dfs(r, c):
   if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0:
       return 0
   grid[r][c] = 0  # Mark as visited
   area = 1
   area += dfs(r - 1, c)
   area += dfs(r + 1, c)
   area += dfs(r, c - 1)
   area += dfs(r, c + 1)
   return area
```
- English: The dfs function explores all connected ‘1’s starting from a given cell (r, c), marking them as visited by setting their value to ‘0’ and calculating the area of the island.
- Chinese: dfs 函数从给定的单元格 (r, c) 开始，探索所有连接的 ‘1’，通过将它们的值设置为 ‘0’ 来标记为已访问，并计算岛屿的面积。
Calculate Maximum Area / 计算最大面积
```
max_area = 0
for r in range(len(grid)):
   for c in range(len(grid[0])):
       if grid[r][c] == 1:
           max_area = max(max_area, dfs(r, c))
```
- English: We iterate through the grid, and for each ‘1’ that we find, we start a DFS to calculate the area of the island. We update max_area with the largest area found.
- Chinese: 我们遍历网格，对于找到的每个 ‘1’，我们开始 DFS 来计算岛屿的面积。我们使用找到的最大面积更新 max_area。
Return the Maximum Area / 返回最大面积
```
return max_area
```
- English: After traversing the entire grid, we return the maximum area of any island found.
- Chinese: 在遍历整个网格后，我们返回找到的任何岛屿的最大面积。

Approach 2: Breadth-First Search (BFS) / 广度优先搜索 (BFS)

Alternatively, BFS can be used to explore and calculate the area of each island. This approach uses a queue to explore all connected ‘1’s iteratively.

另外，可以使用 BFS 来探索和计算每个岛屿的面积。这种方法使用队列以迭代方式探索所有连接的 ‘1’。

BFS Implementation / BFS 实现

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def bfs(r, c):
            queue = deque([(r, c)])
            area = 0
            while queue:
                x, y = queue.popleft()
                if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:
                    continue
                grid[x][y] = 0  # Mark as visited
                area += 1
                queue.append((x - 1, y))
                queue.append((x + 1, y))
                queue.append((x, y - 1))
                queue.append((x, y + 1))
            return area

        max_area = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    max_area = max(max_area, bfs(r, c))

        return max_area

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(m * n), where m is the number of rows and n is the number of columns. We potentially visit every cell once.
Space Complexity / 空间复杂度: O(m * n) in the worst case due to the recursion stack for DFS or the queue for BFS.

Key Concept / 关键概念

Island Area Calculation / 岛屿面积计算: This technique involves exploring and counting all connected land cells in a grid to determine the area of an island, using either DFS or BFS.
岛屿面积计算: 这种技术涉及在网格中探索和计数所有连接的陆地单元格，以确定岛屿的面积，可以使用 DFS 或 BFS。

Summary / 总结

English: Calculating the maximum area of an island can be efficiently implemented using DFS or BFS, depending on the grid size and constraints.
Chinese: 根据网格的大小和约束条件，使用 DFS 或 BFS 可以高效地实现岛屿最大面积的计算。

Tips / 提示

English: Practice both DFS and BFS on grid problems to understand their application in exploring and calculating connected components like islands.
Chinese: 在网格问题上练习 DFS 和 BFS，以理解它们在探索和计算连接组件（如岛屿）中的应用。

Solution Template for Similar Questions / 提示

English: Use DFS or BFS when you need to explore or calculate the size of connected regions in a grid, such as islands or clusters.
Chinese: 当你需要在网格中探索或计算连接区域的大小时（如岛屿或集群），使用 DFS 或 BFS。

5 More Similar Questions / 推荐5问题

LeetCode 200. Number of Islands
LeetCode 463. Island Perimeter
LeetCode 694. Number of Distinct Islands
[LeetCode 827. Making A Large

Island](https://leetcode.com/problems/making-a-large-island/)
LeetCode 1020. Number of Enclaves

Recommended Resources / 推荐资源

English: Practice problems that involve DFS or BFS to strengthen your understanding of how to explore and calculate areas in grid-based problems.
Chinese: 练习涉及 DFS 或 BFS 的问题，以加强你对如何在基于网格的问题中探索和计算面积的理解。

Post Views: 45

CODEBITWAVE