Leetcode——岛屿的最大面积

1. 题目链接：695. 岛屿的最大面积

2. 题目描述：

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

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

示例 1：

输入：grid = [[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]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
1
2
3

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
1
2

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 为 0 或 1，

3. 解法（递归）：

3.1 算法思路：

1. 遍历整个矩阵，每当遇到一块土地的时候，就用深度优先遍历或者宽度优先遍历将与这块土地相连的整个岛屿的面积计算出出来
2. 然后在搜索得到的所有岛屿面积求一个最大值即可
3. 在搜索过程中，为了防止搜到重复的土地：
   1. 可以开一个同等规模的布尔数组，标记以下这个位置是否已经被访问过
   2. 也可以将原始矩阵的1修改成0，但是这样的操作会修改原始矩阵

3.2 算法流程：

主函数内：

1. 遍历整个数组，发现一块没有遍历到的土地之后，就用dfs将于这块土地相连的岛屿的面积求出来
2. 然后将面积更新到最终结果ret中

深度搜索dfs中：

1. 能够进到dfs函数中，说明是一个没遍历到的位置
2. 标记一下已经遍历过，设置一个变量count，记录最终的面积
3. 上下左右遍历四个位置：如果找到一块没有遍历到的土地，就将这块土地相连的岛屿面积累加到count上
4. 循环结束后，count中存的就是这块岛屿的面积，返回即可

3.3 C++算法代码：

class Solution {
    bool vis[51][51]; // 访问标记数组，用于记录某个位置是否已经访问过
    int m, n; // 网格的行数和列数
    int dx[4] = {0, 0, 1, -1}; // x轴方向的偏移量
    int dy[4] = {1, -1, 0, 0}; // y轴方向的偏移量
    int count; // 当前岛屿的面积
public:
    // 计算给定网格中最大的岛屿面积
    int maxAreaOfIsland(vector>& grid) {
        m = grid.size(), n = grid[0].size();
        int ret = 0; // 最大岛屿面积
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && grid[i][j] == 1) { // 如果当前位置未被访问且为陆地
                    count = 0; // 重置岛屿面积
                    dfs(grid, i, j); // 进行深度优先搜索
                    ret = max(ret, count); // 更新最大岛屿面积
                }
            }
        }
        return ret; // 返回最大岛屿面积
    }
    // 深度优先搜索函数，用于计算岛屿面积
    void dfs(vector>& grid, int i, int j) {
        count++; // 当前位置为陆地，岛屿面积加一
        vis[i][j] = true; // 标记当前位置已访问
        for (int k = 0; k < 4; k++) { // 遍历四个方向
            int x = i + dx[k], y = j + dy[k]; // 计算下一个位置的坐标
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) { // 如果下一个位置在网格范围内且未被访问且为陆地
                dfs(grid, x, y); // 继续深度优先搜索
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35