leetcode.200 岛屿数量（DFS）

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

> #### 我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的，而岛屿问题是在一种「网格」结构中进行的。 ####
> 
> #### 有所不同但也可以类比进行分析。 ####
> 
> #### 以lc200为例，写一下分析过程。 ####

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

*  #### 边界条件（退出条件） ####
    
    经常用`if(!root)`
 *  #### 扩散方式 ####
    
    一般是 `dfs(root.left) dfs(root.right)`

## 如果是grid网格结构，则 ##

*  #### 边界条件 ####
    
    四个边不出界
 *  #### 扩散方式 ####
    
    每次向四个方向上扩散

# **以lc200为例** #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

## 边界条件： ##

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

## 扩散方法： ##

dfs(i+1,j,grid);
        dfs(i,j-1,grid);
        dfs(i-1,j,grid);
        dfs(i,j+1,grid);

/** * @param {character[][]} grid * @return {number} */
    var numIslands = function(grid) { 
        let res =0;
        for(let i=0;i<grid.length;i++){ 
            for(let j=0;j<grid[0].length;j++){ 
                if(grid[i][j]=='1'){ 
                    dfs(i,j,grid);
                    res++;
                }
            }
        }
        return res;
    };
    function dfs(i,j,grid){ 
    //边界条件
        if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!=='1'){ 
            return ;
        }
        //将每一个遍历过的岛屿标记成2，不要标记成0，遍历即沉会破坏原结构，标记成2还能恢复。
        grid[i][j]='2';
        dfs(i+1,j,grid);
        dfs(i,j-1,grid);
        dfs(i-1,j,grid);
        dfs(i,j+1,grid);
    }

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

时间复杂度O（m\*n）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221021/bc1cc077f9cf433da4a540defc87bd2a.png