[LeetCode]200. 岛屿数量（java实现）flood fill算法 dfs实现

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

思路（flood fill算法 dfs实现）：
用dfs枚举整个地图，若当前位置是 1，则把这个位置赋值为 # ，然后遍历上下左右四个方向，将所有为1的地方赋值为 #，当这块岛屿已经遍历完，则 答案加1 。

flood fill算法大致框架：

---------------------------------------------------解法---------------------------------------------------

class Solution {
    int res = 0;
    int n,m;
    int[] dx = new int[]{1,0,-1,0};
    int[] dy = new int[]{0,-1,0,1};
    public int numIslands(char[][] grid) {
        n = grid.length;
        if(n == 0) return res;
        m = grid[0].length;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                // 遍历每一个位置，如果当前位置是1，则进行dfs将所有与之相连为1的地方都置为#，表示被遍历过
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
        return res;
    }
    // dfs遍历所有与之相连为1的地方
    public void dfs(char[][] grid,int x,int y){
        grid[x][y] = '#';
        // 遍历四个方向
        for(int i = 0;i < 4;i++){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >=n || b < 0 || b >= m) continue;
            if(grid[a][b] == '1') dfs(grid,a,b);
        }
    }
}

可能存在的问题：

• [LeetCode]130. 被围绕的区域（java实现）flood fill 泛洪算法 dfs实现

• flood fill 算法
• 用数组表示四个方向上的偏移量

flood fill 算法的dfs实现，模板题，背下来！