沙井网站优化,大庆工程建设公司网站,免费营销型企业网站模板,简易网站建设本题是让求岛屿的最大面积#xff0c;和上一个题求岛屿的数量类似#xff0c;也是通过dfs或者bfs进行求解。
那么#xff0c;首先我们判断dfs函数的参数#xff0c;需要grid[][]#xff0c;需要横坐标i#xff0c;纵坐标j。那么#xff0c;这里我们求的是最大面积… 本题是让求岛屿的最大面积和上一个题求岛屿的数量类似也是通过dfs或者bfs进行求解。
那么首先我们判断dfs函数的参数需要grid[][]需要横坐标i纵坐标j。那么这里我们求的是最大面积我们需要把每一次递归所求的的面积都返回给调用者所以这里我们需要返回值并且是int类型。
然后我们确定终止条件也就是当我们走到边界或者走到的当前位置是海洋值为0那么我们直接return0即可因为没有找到岛屿。
然后我们确定单层递归的逻辑。注意这里我们可以把我们已经走过的陆地值为1的点置为0从而省去标记的二维数组。然后我们可以在当前值为1的点判断其上下左右是不是1如果是则面积1如果不是则不需要处理
然后我们在函数中先进行两次for循环是为了在图中找到值为1的点先找到一块陆地然后进行dfs再把返回值和0作比较返回二者中最大值即可
//这里使用深度优先搜索 DFS 来完成本道题目。我们使用 DFS 计算一个岛屿的面积同时维护计算过的最大的岛屿面积。同时为了避免对岛屿重复计算我们在 DFS 的时候对岛屿进行 “淹没” 操作即将岛屿所占的地方置为 0。
public int maxAreaOfIsland(int[][] grid) {int res 0;for(int i 0;i grid.length;i){for(int j 0;j grid[0].length;j){//每遇到一个岛屿就计算这个岛屿的面积同时”淹没“这个岛屿if(grid[i][j] 1){//每次计算一个岛屿的面积都要与res比较维护最大的岛屿面积作为最后的答案res Math.max(res,dfs(grid,i,j));}}}return res;
}
public int dfs(int[][] grid,int i,int j){//搜索边界ij超过grid的范围或者当前元素为0即当前所在的地方已经是海洋if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) return 0;//淹没土地防止后续被重复计算grid[i][j] 0;//递归的思路要求当前土地(i,j)所在的岛屿的面积则等于1加上下左右相邻的土地的总面积return 1 dfs(grid,i - 1,j) dfs(grid,i 1,j) dfs(grid,i,j 1) dfs(grid,i,j - 1);
}
