- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
深度优先遍历
先明确，题意要求我们找到矩阵中的岛屿数量，上下左右相连接的 '1' 是连续的 1 座岛屿。
- 从起点 (i, j) 的上下左右四个方向进行深度搜索。
- 搜索过程中，将搜索过的岛屿标记为 '0'。
- 遍历整个矩阵，当
grid[i][j] === '1'时，进行搜索并且将岛屿数加 1。 - 注意递归终止条件
constnumIslands=function(grid){constdfs=function(grid,i,j){if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==='0'){return}grid[i][j]='0'dfs(grid,i+1,j)dfs(grid,i,j+1)dfs(grid,i-1,j)dfs(grid,i,j-1)}letcount=0for(leti=0;i<grid.length;i++){for(letj=0;j<grid[0].length;j++){if(grid[i][j]==='1'){dfs(grid,i,j)count++}}}returncount}
- 时间复杂度：O(m * n)
- 空间复杂度：O(m * n)