695.岛屿的最大面积\huge{695.岛屿的最大面积}695.岛屿的最大面积

原题目

标签

StackStackStack、深度优先搜索、方向变量、递归

带有注解的代码

class Solution {
public:vector direction{-1,0,1,0,-1};int maxAreaOfIsland(vector>& grid) {//深度优先遍历：//方法一：使用stack进行深度优先搜索int m = grid.size();                //行长度int n = m ? grid[0].size() : 0;     //列长度int local_area;                     //每次点(i,j)进行测试的时候存放最大值int area = 0;                       //存放最后的最大值int x;int y;for(int i = 0 ; i < m ; i++)            //从每个点开始进行遍历{for(int j = 0 ; j < n ; j++){if(grid[i][j])              //如果这个点在当前地图中是陆地则可以开始进行拓展{local_area = 1;         //算了初始脚下的这片面积了grid[i][j] = 0;         //标志更改//stack中使用的是二元组是为了保存的时候将两个坐标同时进行保存stack> island;island.push({i,j});        //首个陆地加入到栈中while(!island.empty())      {auto [r,c] = island.top();      //取出栈顶元素island.pop();for(int k = 0 ; k < 4 ; k++)       //遍历四个方向{x = r + direction[k];y = c + direction[k+1];//只有既不超过范围，并且也是陆地的方块才能够进行加入if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){grid[x][y] = 0;++local_area;island.push({x,y});}}}area = max(area,local_area);            //遍历完一个点之后取最值}}}return area;------------------------------------------------------------------------------------//方法二：使用系统递归调用//调用递归主函数  if(grid.empty() || grid[0].empty())return 0;int max_area = 0;for(int i = 0 ; i < grid.size() ; i++){for(int j = 0 ; j < grid[0].size() ; j++){if(grid[i][j] == 1)max_area = max(max_area,dfsTwo(grid,i,j));//dfsOne(grid,i,j);}}return max_area;}//递归函数写法一：//拓展的时候顺带进行判断，如果不符合条件直接去除int dfsOne(vector>& grid , int r ,int c){if(grid[r][c] == 0)return 0;grid[r][c] = 0;int x;int y;int area = 1;for(int i = 0 ; i < 4 ; i++){x = r + direction[i];y = c + direction[i+1];//拓展的时候进行条件判断if(x >= 0 && x < grid.size() && y >= 0 && grid[0].size())       area += dfsOne(grid,x,y);}return area;}//递归函数写法二：//拓展的时候直接拓展，之后进入到下一个递归层在判断这样拓展符不符合条件int dfsTwo(vector>& grid,int r,int c){if(r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0)        //判断上一层是否符合条件return 0;grid[r][c] = 0;//直接递归省去了方向标志的创建return 1 + dfsTwo(grid,r + 1 ,c) + dfsTwo(grid,r - 1,c) + dfsTwo(grid,r,c + 1) + dfsTwo(grid,r,c - 1);}
};