200. 岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用并查集

class Solution {
    /**
     * 使用并查集
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        // 初始化并查集对象
        UnionFind uf = new UnionFind(m * n);
        // 遍历所有的岛屿，合并岛屿
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    // 岛屿数量减1
                    uf.decCount();
                    continue;
                }
                // 与左边的岛屿合并
                if (i > 0 && grid[i - 1][j] == '1') {
                    uf.union((i - 1) * n + j, i * n + j);
                }
                // 与上面的岛屿合并
                if (j > 0 && grid[i][j - 1] == '1') {
                    uf.union(i * n + (j - 1), i * n + j);
                }
            }
        }
        return uf.getCount();
    }

    class UnionFind {
        int[] roots;    // 存储并查集
        int count = 0;  // 岛屿个数

        public UnionFind(int n) {
            roots = new int[n];
            // 初始化并查集
            for (int i = 0; i < n; i++) {
                // 并查集节点自己指向自己
                roots[i] = i;
                count ++;
            }
        }

        /**
         * 获取root
         *
         * @param p
         * @return
         */
        public int findRoot(int p) {
            // 获取root
            int root = p;
            while (root != roots[root]) {
                root = roots[root];
            }
            // 缩短路径，将路径上的所有节点的root全部赋为找到root
            int i = p;
            while (i != roots[i]) {
                int tmp = roots[i];
                roots[i] = root;
                i = tmp;
            }
            return root;
        }

        /**
         * 合并
         *
         * @param p1
         * @param p2
         */
        public void union(int p1, int p2) {
            int root1 = findRoot(p1);
            int root2 = findRoot(p2);
            if (root1 != root2) {
                roots[root2] = root1;
                // 两个岛屿合并，计数减1
                decCount();
            }
        }

        public void decCount() {
            count --;
        }

        public int getCount() {
            return count;
        }
    }

    public static void main(String[] args) {
        char[][] grids = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        int result = new Solution().numIslands(grids);
        System.out.println(result);
    }
}

运行效率

DFS深度优先搜索

class Solution {
    private char[][] grid;
    private boolean[][] visited; // 已经浏览过的岛屿
    private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int row;    // 行
    private int column; // 列

    /**
     * DFS
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        this.grid = grid;
        this.row = grid.length;
        this.column = grid[0].length;
        this.visited = new boolean[row][column];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (visited[i][j] || grid[i][j] == '0') {
                    continue;
                }
                visit(i, j);
                count ++;
            }
        }
        return count;
    }

    /**
     * DFS深度优先搜索，找到一个就延四个方向深入搜索
     *
     * @param x
     * @param y
     */
    private void visit(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < direction.length; i++) {
            int dirX = direction[i][0];
            int dirY = direction[i][1];
            if (x + dirX < 0 || x + dirX >= row || y + dirY < 0 || y + dirY >= column
                    || visited[x + dirX][y + dirY] || grid[x + dirX][y + dirY] == '0') {
                continue;
            }
            visit(x + dirX, y + dirY);
        }
    }
}

运行效率

BFS广度优先搜索

class Solution {
    private char[][] grid;
    private boolean[][] visited;
    private int row;
    private int column;
    // 存储坐标(x, y) 的计算值，需要能够通过值得到 (x, y)
    // value = x * row * column + y
    // y = value % (row * column)
    // x = (value - y) / (row * column)
    private Queue<Integer> queue;
    private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int count = 0;

    /**
     * BFS广度优先搜索
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        this.grid = grid;
        this.row = grid.length;
        this.column = grid[0].length;
        this.visited = new boolean[row][column];
        this.queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    visited[i][j] = true;
                    queue.add(i * (row * column) + j);
                    visit();
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * BFS广度优先搜索
     */
    private void visit() {
        while (!queue.isEmpty()) {
            int position = queue.remove();
            int y = position % (row * column);
            int x = (position - y) / (row * column);
            for (int[] dir : direction) {
                int dirX = dir[0];
                int dirY = dir[1];
                if (validPosition(x + dirX, y + dirY)
                        && !visited[x + dirX][y + dirY] && grid[x + dirX][y + dirY] == '1') {
                    visited[x + dirX][y + dirY] = true;
                    queue.add((x + dirX) * row * column + (y + dirY));
                }
            }
        }
    }

    /**
     * 校验坐标是否合法
     *
     * @param x
     * @param y
     * @return
     */
    private boolean validPosition(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < column;
    }

    public static void main(String[] args) {
        char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        int result = new Solution().numIslands(grid);
        System.out.println(result);
    }
}

运行效率