当前位置: 首页 > Web前端 > HTML

【leetcode】剑指OfferII105.最大面积的岛屿-【深度优先DFS】

时间:2023-03-28 18:28:53 HTML

给定一个由0和1组成的非空二维数组网格,用来表示海洋岛屿地图。岛屿是一些相邻的1(代表陆地)的组合。这里的“相邻”要求两个1在水平或垂直方向上必须相邻。您可以假设网格的所有四个边都被零(代表水)包围。在给定的二维数组中找到最大的岛屿面积。如果没有岛屿,则返回的面积为0。示例1:输入:grid=[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输出:6解释:对于上面给定的矩阵,应该返回6。请注意,答案不应为11,因为该岛只能在四个方向(水平或垂直)上包含1。示例2:输入:grid=[[0,0,0,0,0,0,0,0]]输出:0提示:m==grid.lengthn==grid[i].length1<=m,n<=50grid[i][j]iseither0or1解题思路是遍历并记录已访问和未访问的岛屿;岛屿的数量,并将当前岛屿设置为已访问;根据大岛,更新小岛记录解题代码及其注释/***@param{number[][]}grid*@return{number}*/varmaxAreaOfIsland=function(grid){letcol=grid.length,row=grid[0].length,max=0;//row,column//未访问的岛为1,已访问的岛为0设matrix=[...Array(col)].fill(0).map(()=>[...Array(row)]。fill(1))letdfs=(i,j)=>{//边界if(i<0||i>=col||j<0||j>=row)return0;让ret=0;lettemp=matrix[i][j]//isislandmatrix[i][j]=0//访问过的岛屿标记为0if(grid[i][j]&&temp){ret+=dfs(i+1,j)//下一个ret+=dfs(i-1,j)//上ret+=dfs(i,j+1)//右ret+=dfs(i,j-1)//左ret++}returnret}for(leti=0;i