[数据结构与算法]Leetcode 695. 岛屿的最大面积

今天学习了深度优先搜索，题目如下

695. 岛屿的最大面积

难度中等673

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

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

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

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

?

写这题的思路是，遍历每一个含有陆地的岛屿，如果遍历过的话，把该陆地改成水，以防遍历重复了，之后的思路在代码中解释。

class Solution {
public:
int n,m;
int  dfs(vector<vector<int>>& grid, int x, int y){
if(x<n&&x>=0&&y>=0&&y<m) //防止越界//
{
    if(grid[x][y]==0)
    return 0;//该循环有两个界限，一个是原本数组的界限，还有一个是陆地和水的界限，我们只遍历陆地//
    else
    {
        grid[x][y]=0;//把遍历过的改为水，并且答案加1，遍历上下左右四个方向//
        return 1+dfs(grid,x-1,y)+dfs(grid,x+1,y)+dfs(grid,x,y+1)+dfs(grid,x,y-1);
    }   
}
else
{
    return 0;
}
}
    int maxAreaOfIsland(vector<vector<int>>& grid) {
n=grid.size();
m=grid[0].size();
int ans=0;//生成一个答案，来记录每块陆地的值来比较//
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        ans=max({ans,dfs(grid,i,j)}); //比较每块陆地的值
    }
}
return ans;
    }
};

?