695.岛屿的最大面积

发表于： 分类于：
字数： 1037 阅读：≈ 3分钟

👏 695.岛屿的最大面积

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

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

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

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

思路

基本思想

主要的思想就是遍历整个图，将岛屿找出来，同时需要将岛屿中的面积计算出来，从而找出最大的面积，所以分为以下几步：

  1. 找出岛屿：

    只需要遵循二叉树的遍历思路，一旦遇到一个陆地，将陆地遍历一下，然后已遍历的陆地进行标记，在该陆地的上下左右找是否存在相邻的陆地，将所有相邻的陆地找出来，才算是形成一个岛屿

  2. 计算岛屿的面积：

    为了计算面积，岛屿中的一块陆地的面积为1，所以只需要将岛屿中的所有陆地统计出来即可，在遍历岛屿中所有的陆地时，遇到一个没有遍历的陆地，岛屿的面积应该+1，当岛屿中所有的陆地都被访问过之后，就得到了岛屿最终的面积

  3. 找出最大的面积：

    为了找出最大的面积，每计算出一个面积，都需要判断当前面积是否是最大的，所以需要定义一个全局变量来存储最终的面积

经过以上步骤，就可以得到最终的结果

执行流程

  1. 遍历给定的图，出现一块陆地，将其相邻的所有陆地找出来形成一个岛
  2. 为了形成一个岛，需要从当前的陆地出发进行遍历，需要借助一个函数
  3. 进入当前函数时，如果当前的位置超过范围，或者是海洋，亦或者是已遍历的陆地，直接返回
  4. 当当前陆地没有被遍历，那么就需要遍历当前陆地，然后从当前陆地出发，遍历上下所有，查看是否存在陆地
  5. 遍历之前需要注意，当前的陆地面积为1，所以岛屿的面积应该+1
  6. 遍历结束之后，岛屿的面积统计到了，此时需要判断岛屿的面积是否是全局最大的面积
  7. 返回全局最大的面积

代码

根据以上分析，得出以下代码：

 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
36

class Solution {
public:
    int res=0;//如果没法更新，说明没有岛屿，此时返回0
    //遇到一个陆地，就将相邻的陆地找出来，遇到一个没遍历过的陆地，面积+1
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]==1){
                    int area=0;
                    dfs(grid,area,i,j);
                    //看是不是更大的陆地
                    res=max(res,area);
                }
            }
        }
        //返回最大的面积
        return res;
    }
    //为了岛屿的面积能够记录，这里应该传递引用
    void dfs(vector<vector<int>>& grid,int& area,int x,int y){
        //超出边界，遇到海洋，已遍历的陆地都会直接返回
        if(x<0||y<0||x>=grid.size()||y>=grid[0].size()||
        grid[x][y]==0||grid[x][y]==2)
            return;
        //到这里说明找到一个未遍历的陆地
        grid[x][y]=2;
        //面积+1
        area+=1;
    
        //遍历当前位置的上下左右，看能不能找到新的陆地
        dfs(grid,area,x-1,y);
        dfs(grid,area,x+1,y);
        dfs(grid,area,x,y-1);
        dfs(grid,area,x,y+1);
    }
};

总结

对二叉树的遍历稍加修改，并且未遍历的陆地面积为1，所以岛屿的面积应该+1