leetcode.200 岛屿数量（DFS）

﹏ヽ暗。殇╰゛Y 2022-10-21 14:00 204阅读 0赞

我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的，而岛屿问题是在一种「网格」结构中进行的。

有所不同但也可以类比进行分析。

以lc200为例，写一下分析过程。

常见的DFS应用二叉树结构，有两个重点

  • 边界条件（退出条件）

    经常用if(!root)

  • 扩散方式

    一般是 dfs(root.left) dfs(root.right)

如果是grid网格结构，则

  • 边界条件

    四个边不出界

  • 扩散方式

    每次向四个方向上扩散

以lc200为例

在这里插入图片描述

边界条件：

  1. if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!=='1'){ 
  2.         return ;
  3.     }

扩散方法：

  1. dfs(i+1,j,grid);
  2.     dfs(i,j-1,grid);
  3.     dfs(i-1,j,grid);
  4.     dfs(i,j+1,grid);
  6. /** * @param {character[][]} grid * @return {number} */
  7. var numIslands = function(grid) { 
  8.     let res =0;
  9.     for(let i=0;i<grid.length;i++){ 
  10.         for(let j=0;j<grid[0].length;j++){ 
  11.             if(grid[i][j]=='1'){ 
  12.                 dfs(i,j,grid);
  13.                 res++;
  14.             }
  15.         }
  16.     }
  17.     return res;
  18. };
  19. function dfs(i,j,grid){ 
  20. //边界条件
  21.     if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!=='1'){ 
  22.         return ;
  23.     }
  24.     //将每一个遍历过的岛屿标记成2，不要标记成0，遍历即沉会破坏原结构，标记成2还能恢复。
  25.     grid[i][j]='2';
  26.     dfs(i+1,j,grid);
  27.     dfs(i,j-1,grid);
  28.     dfs(i-1,j,grid);
  29.     dfs(i,j+1,grid);
  30. }

注：没有将遍历过的岛屿变成0，即遍历即沉。为了保持原结构，标记置位2，如有需还能恢复原结构。

时间复杂度O（m*n）

发表评论

表情：
评论列表 （有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode200. 岛屿数量

    给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包

    今天药忘吃喽~今天药忘吃喽~/ 0 赞/ 53 阅读

    相关 【leetcode.200】岛屿数量

    一、题目描述 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地

    秒速五厘米秒速五厘米/ 0 赞/ 234 阅读

    相关 LeetCode200. 岛屿数量

    题目难度：中等 题目描述： > 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 > 岛屿总是被水包围，并且每座岛屿只能由水平方

    小咪咪小咪咪/ 0 赞/ 227 阅读