每日一道算法题之岛屿数量-洪水填充

class Solution {

    public static void main(String[] args) {
        new Solution().numIslands(new char[][] { { '1', '0', '1', '1', '0', '1', '1' } });
    }

    public void f(int i, int j, char[][] grid) {

        // 递归结束条件 注意这里要看边界值+以及是字符不是int 0.
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            // 遇到边界+值为'0'，直接返回
            return;
        }
        grid[i][j] = '0'; // 渲染为0.

        // 向四个方向渲染。
        f(i + 1, j, grid);
        f(i, j + 1, grid);
        f(i - 1, j, grid);
        f(i, j - 1, grid);
    }

    public int numIslands(char[][] grid) {
        // 思路：并查集。每个坐标来确定唯一的索引。
        // 思路2：洪水填充。
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    f(i, j, grid);
                }
            }
        }
        System.out.println(ans);
        return ans;
    }
}