LC200—岛屿数量

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

class Solution {
   
   public int numIslands(char[][] grid) {
   
    //边界条件判断
    if (grid == null || grid.length == 0)
        return 0;
    //统计岛屿的个数
    int count = 0;
    //两个for循环遍历每一个格子
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++) {
   
            //只有当前格子是1才开始计算
            if (grid[i][j] == '1') {
   
                //如果当前格子是1，岛屿的数量加1
                count++;
                //然后通过dfs把当前格子的上下左右4
                //个位置为1的都要置为0，因为他们是连着
                //一起的算一个岛屿，
                dfs(grid, i, j);
            }
        }
    //最后返回岛屿的数量
    return count;
}

//这个方法会把当前格子以及他邻近的为1的格子都会置为1
public void dfs(char[][] grid, int i, int j) {
   
    //边界条件判断，不能越界
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
        return;
    //把当前格子置为0，然后再从他的上下左右4个方向继续遍历
    grid[i][j] = '0';
    dfs(grid, i - 1, j);//上
    dfs(grid, i + 1, j);//下
    dfs(grid, i, j + 1);//左
    dfs(grid, i, j - 1);//右
}

}

package com.nie.o3;/* * *@auth wenzhao *@date 2021/3/8 21:23 */

public class LEE200 {
   
    private static final int[][] DIR = {
   {
   -1, 0}, {
   0, 1}, {
   0, -1,}, {
   1, 0}};
    private boolean[][] visited;
    private int rows;
    private int cols;
    private char[][] grid;

    public int numIsland(char[][] grid) {
   
        this.rows = grid.length;
        this.cols = grid[0].length;
        if (rows == 0) {
   
            return 0;
        }
        this.visited = new boolean[rows][cols];
        int count = 0;
        this.grid = grid;
        for (int i = 0; i < rows; i++) {
   
            for (int j = 0; j < cols; j++) {
   
                if (grid[i][j] == '1' & !visited[i][j]) {
   
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j) {
   
        visited[i][j] = true;
        for (int k = 0; k < DIR.length; k++) {
   
            int newX = i + DIR[k][0];
            int newY = j + DIR[k][1];

            // 如果不越界、还是陆地、没有被访问过
            if (inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
   
                dfs(newX, newY);
            }

        }
    }

    private boolean inArea(int x, int y) {
   
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

}

public class Solution {
   

    private int rows;
    private int cols;

    public int numIslands(char[][] grid) {
   
        rows = grid.length;
        if (rows == 0) {
   
            return 0;
        }
        cols = grid[0].length;

        // 空地的数量
        int spaces = 0;
        UnionFind unionFind = new UnionFind(rows * cols);
        int[][] directions = {
   {
   1, 0}, {
   0, 1}};
        for (int i = 0; i < rows; i++) {
   
            for (int j = 0; j < cols; j++) {
   
                if (grid[i][j] == '0') {
   
                    spaces++;
                } else {
   
                    // 此时 grid[i][j] == '1'
                    for (int[] direction : directions) {
   
                        int newX = i + direction[0];
                        int newY = j + direction[1];
                        // 先判断坐标合法，再检查右边一格和下边一格是否是陆地
                        if (newX < rows && newY < cols && grid[newX][newY] == '1') {
   
                            unionFind.union(getIndex(i, j), getIndex(newX, newY));
                        }
                    }
                }
            }
        }
        return unionFind.getCount() - spaces;
    }

    private int getIndex(int i, int j) {
   
        return i * cols + j;
    }

    private class UnionFind {
   
        /** * 连通分量的个数 */
        private int count;
        private int[] parent;

        public int getCount() {
   
            return count;
        }

        public UnionFind(int n) {
   
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
   
                parent[i] = i;
            }
        }

        private int find(int x) {
   
            while (x != parent[x]) {
   
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public void union(int x, int y) {
   
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot == yRoot) {
   
                return;
            }

            parent[xRoot] = yRoot;
            count--;
        }
    }
}