LeetCode0695-海岛岛屿最大面积
深度搜索
经典之海岛岛屿
题目
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
题解
注意，要我们计算的是最大的海岛岛屿面积，而不是这篇区域的面积和
我们先一步步来，首先对于每一点，我们要怎么进行上下左右的搜索呢？
//public static void dfs(地图，坐标x,坐标y)public static void dfs(int[][] grid，int _x,int _y){//老规矩，判断if(_x<0 || _y<0 || _x>=grid.length || _y >=grid[0].length){return ;//越界自然是不行的}if(grid[_x][_y] ==0){return ;//是海的话，我们也不要进行什么操作}grid[_x][_y] = 0 ; //更改属性(地->海)，避免重复计算dfs(gird,_x+1,_y);dfs(gird,_x-1,_y);dfs(gird,_x,_y+1);dfs(gird,_x,_y-1);}
好的，现在我们回过头来看，我们需要的是最大岛屿面积
思路很简单，算出每个小岛屿的面积和即可，然后不断比较更新最大值
int max = 0 ; Math.max(max,每个岛屿的面积);
因此我们改造以下dfs函数，使它可以返回每一个岛屿的面积
public static int dfs(int[][] grid, int _x, int _y){if(_x<0 || _y<0 || _x>=grid.length || _y >=grid[0].length){return 0 ;}if(grid[_x][_y] ==0){return 0 ;}//是陆地的话就对周围计数int count = 1 ;grid[_x][_y] = 0 ;count += dfs(grid,_x+1,_y);count += dfs(grid,_x,_y+1);count += dfs(grid,_x-1,_y);count += dfs(grid,_x,_y-1);return count ;}
然后我们遍历地图，就可以求得最大值
int max = 0 ;//遍历比较for(int i = 0 ; i完整的代码如下:
class Solution {public int maxAreaOfIsland(int[][] grid) {int max = 0 ;//遍历比较for(int i = 0 ; i=grid.length || _y >=grid[0].length){return 0 ;}if(grid[_x][_y] ==0){return 0 ;}int count = 1 ;grid[_x][_y] = 0 ;count += dfs(grid,_x+1,_y);count += dfs(grid,_x,_y+1);count += dfs(grid,_x-1,_y);count += dfs(grid,_x,_y-1);return count ;}
}
s
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！