200. 岛屿数量(一般)

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i] [j] 的值为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

思路1：

DFS

基本思路

  • 扫描整个网格，把找到的第一个位置为‘1’的节点作为起始节点，并开始深度优先搜索
  • 在DFS的过程中，每个被找到的‘1’都会被重新标记为‘0’
  • DFS总结完就三大要素：终止条件，做选择 &下一层递归

作者：weichen-wang
链接：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-unionfindbing-cha-ji-by-weichen-7ldae/

思路2：

BFS

思路3：

并查集，遍历部分不是很理解

代码1&2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
    public int numIslands(char[][] grid) {
        //base
        if (grid.length == 0 || grid == null) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        //岛屿计数
        int count = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                //如果找到1的时候，开始dfs
                if(grid[i][j]=='1'){
                    count++;
                    dfs(grid,i,j);
                    //bfs(grid,i,j);
                }
            }
        }
        return count;
    }
    //dfs
    void dfs(char[][] grid,int row,int col){
        //注意终止条件
        //行超过，列超过,或者找到的点就是0
        if(row<0 || row>= grid.length
        || col<0 || col>= grid[0].length
        || grid[row][col]=='0'){
            return;
        }
        //开始染色，将当前的1转成0
        grid[row][col]='0';
        //开始下一层深搜
        dfs(grid,row-1,col);
        dfs(grid,row+1,col);
        dfs(grid,row,col-1);
        dfs(grid,row,col+1);
    }
    //bfs
    void bfs(char[][] grid,int row,int col){
        //队列
        Queue<int[]> queue = new LinkedList<>();
        //访问标识
        //Set<int[]> visited = new HashSet<>();
        //添加根进去
        queue.add(new int[]{row,col});
        //visited.add(new int[]{row,col});

        while (!queue.isEmpty()){
            //弹出当前的
            int[] cur = queue.poll();
            //获取cur的x，y坐标，可以用row和col接收
            row = cur[0];
            col = cur[1];
            //判断是否访问,如果已经访问了直接返回
            //if(visited.contains(cur)){
            //    return;
            //}
            //上下左右扩散，加入
            //&&顺序不能改
            if(row-1>=0 && grid[row-1][col] == '1'){
                queue.add(new int[]{row-1,col});
                grid[row-1][col]='0';
            }
            if(row+1<grid.length && grid[row+1][col] == '1'){
                queue.add(new int[]{row+1,col});
                grid[row+1][col]='0';
            }
            if(col-1>=0 && grid[row][col-1] == '1'){
                queue.add(new int[]{row,col-1});
                grid[row][col-1]='0';
            }
            if(col+1<grid[0].length && grid[row][col+1] == '1'){
                queue.add(new int[]{row,col+1});
                grid[row][col+1]='0';
            }
        }
    }
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0){
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        //初始化并查集
        UnionFind uf = new UnionFind(row*col);

        int water = 0; // 水域(0)个数

        //遍历
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                //这个搜索是个难题啊，不是很会
                if (grid[i][j] == '0') {
                    water++;
                } else {
                    // '1'的岛屿
                    // 注意: 方向数组 d 是上下左右搜索的常用手法
                    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                    for (int[] dir : directions) {
                        // 当前坐标 向 上下左右方向移动
                        int x = i + dir[0];
                        int y = j + dir[1];
                        // 判断是否越界
                        if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == '1') {
                            // 合并
                            uf.union(i * col + j, x * col + y);
                        }
                    }
                }

            }
        }
        return uf.count - water;
    }
}
//并查集模板
class UnionFind{
    //记录父节点
    int[] parent;
    //记录岛屿个数
    int count;

    //初始化,将自己的父节点指向自己
    public UnionFind(int n){
        parent = new int[n];
        count =n;//每个节点算一个岛屿
        //初始化
        for (int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    //找一个节点的根父节点
    int find(int n){
        //如果自己的父节点不是自己
        while(parent[n]!=n){
            //一直往上找,路径压缩
            parent[n]=parent[parent[n]];
            n= parent[n];
        }
        return n;
    }
    //使用find进行判断
    boolean isConnected(int x,int y){
        return find(x)==find(y);
    }
    //连接两个岛屿
    void union(int x,int y){
        if(find(x)==find(y)){
            return;
        }
        //小树连大树，这里可以进行优化
        parent[find(x)] = find(y);
        count--;//计数器--
    }
}