LeetCode 200：岛屿数量

小半 • 2023年2月3日上午10:52 • 技术随笔 • 阅读 341

链接
题目：

注意： 四周视为海水！

思路：回溯

之前在子集/组合、排列中的回溯框架为：

岛屿问题中的回溯则不太一样；

①用两层for遍历二维数组的每个元素，第一次碰到岛屿时记录数量
②用dfs将与岛屿及其相邻的都淹没，以免重复记数
只有与岛屿之间有海水相隔开（dfs遇到海水return）的岛屿才会再被记数

为什么每次遇到岛屿都要⽤ DFS 算法把岛屿「淹了」呢？
主要是可以避免维护 visited 数组，一旦遇到 ‘0’ 就会return;

dfs的作用仅仅是将岛屿和周围「淹没」！

Java实现：

注意：

判断数组越界时，是 i>=grid.length 而不是 i>grid.length ，i 不能等于数组长度！
dfs中一定要有 if(grid[i][j]=='0'){ return; } ，即遇到海水则不需要再淹没，否则每个点都要去遍历所有元素，导致栈溢出！

class Solution {
    public int numIslands(char[][] grid) {
        int res=0;
        int m=grid.length;
        int n=grid[0].length;
        //遍历grid每个元素
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    //第一次发现岛屿则记数
                    res++;
                    //将岛屿及其相邻的都淹没，以免重复记数
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    void dfs(char[][] grid,int i,int j){
        int m=grid.length;
        int n=grid[0].length;
        if(i<0 || j<0 || i>=m || j>=n){ //终止条件1 ： 超出边界
            return;
        }
        if(grid[i][j]=='0'){ //终止条件2 ：已经是海水
            return;
        }
        //岛屿变为海水
        grid[i][j]='0'; 
        //淹没岛屿四周（上下左右）
        dfs(grid,i-1,j); 
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        }
}