NC109：岛屿数量

参考：
1. https://blog.csdn.net/dongmuyang/article/details/94408324
2. https://www.imooc.com/article/291766
思路：

1. 遍历整块大陆，横着竖着遍历都可以。
2. 第一次碰到陆地的时候，就知道这是块岛屿了，所以将这块陆地放入探险队列，岛屿数量加一。
3. 然后我们将这块岛屿的陆地探索完。每一次将这块陆地周围（上下左右）的陆地放入队列，然后将这块陆地标记为已探索（这里就直接置为'0'了）。
4. 当探险队列为空时，表示这块岛屿的陆地全部被探索完了，我们继续寻找下一块陆地。

BFS用的是队列---DFS用的是栈，所以直接用递归就可以了，用的系统栈；

解法1：DFS
从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点
时间复杂度 : O(M×N)，其中 M 和 N 分别为行数和列数。
空间复杂度 : 最坏情况下为 O(M×N)，此时整个网格均为陆地，深度优先搜索的深度达到 M×N。
（运行结果：返回非零，在LeetCode和本地都可以正确）

public void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int solve(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1' ) {
                    num_islands++;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }

解法2：BFS
从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个顶点

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length, count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < columns; j++) {//遍历所有节点
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, row, columns);
                    count++;//记录岛屿数量
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j, int row, int columns) {
        Queue<Integer> queue = new LinkedList<>();//队列暂存值为 1 的点
        queue.add(i * columns + j);//暂存该点位置，也可以用一个[i,j]数组表示，不过占用空间也会大一倍
        while (!queue.isEmpty()) {
            int id = queue.remove();//取出位置
            int r = id / columns, c = id % columns;//分解位置得到索引
            if (r - 1 >= 0 && grid[r - 1][c] == '1') {
                queue.add((r - 1) * columns + c);
                grid[r - 1][c] = '0';
            }
            if (r + 1 < row && grid[r + 1][c] == '1') {
                queue.add((r + 1) * columns + c);
                grid[r + 1][c] = '0';
            }
            if (c - 1 >= 0 && grid[r][c - 1] == '1') {
                queue.add(r * columns + c - 1);
                grid[r][c - 1] = '0';
            }
            if (c + 1 < columns && grid[r][c + 1] == '1') {
                queue.add(r * columns + c + 1);
                grid[r][c + 1] = '0';
            }
        }
    }
}

解法3：并查集
也被称为联合查找数据结构，因为它主要由联合、查找两个过程实现：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
针对该题即 先以一个根节点1作为初始节点，判断周围节点是否为1，如果是则新建一个集合并把该节点作为父节点。之后遍历下一个节点，如果是1则查找该节点的父节点（即第一个节点），并把该节点周围为1的节点的父节点全部指向该节点的父节点，以此类推，直到把该块岛屿所有1 节点加入同一个集合。最后集合个数（父节点的个数）即为岛屿数量
以下java代码参考自LeetCode，自己不会写

class UnionFind {
        int count; //计数
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length, n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }
        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }
        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }
        public int getCount() {
            return count;
        }
    }
    public int solve(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') uf.union(i * columns + j, (i - 1) * columns + j);
                    if (i + 1 < row && grid[i + 1][j] == '1') uf.union(i * columns + j, (i + 1) * columns + j);
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') uf.union(i * columns + j, i * columns + j - 1);
                    if (j + 1 < columns && grid[i][j + 1] == '1') uf.union(i * columns + j, i * columns + j + 1);
                }
            }
        }
        return uf.getCount();
    }