题目

类型：BFS
难度：中等
image.png

解题思路

  • 深度/广度 优先搜索

扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度/深度优先搜索。
在广度/深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束，这样就保证连着的1只算作一个岛屿。
最终岛屿的数量就是进行搜索的次数。

  • 并查集

扫描整个二维网格。如果一个位置为 11，则将其与相邻四个方向上的 11 在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。

代码

1、深度优先

  1. class Solution {
  2.     void dfs(char[][] grid, int r, int c) {
  3.         int nr = grid.length;
  4.         int nc = grid[0].length;
  6.         if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
  7.             return;
  8.         }
  10.         grid[r][c] = '0';
  11.         dfs(grid, r - 1, c);
  12.         dfs(grid, r + 1, c);
  13.         dfs(grid, r, c - 1);
  14.         dfs(grid, r, c + 1);
  15.     }
  17.     public int numIslands(char[][] grid) {
  18.         if (grid == null || grid.length == 0) {
  19.             return 0;
  20.         }
  22.         int nr = grid.length;
  23.         int nc = grid[0].length;
  24.         int num_islands = 0;
  25.         for (int r = 0; r < nr; ++r) {
  26.             for (int c = 0; c < nc; ++c) {
  27.                 if (grid[r][c] == '1') {
  28.                     ++num_islands;
  29.                     dfs(grid, r, c);
  30.                 }
  31.             }
  32.         }
  34.         return num_islands;
  35.     }
  36. }

2、广度优先

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.         if (grid == null || grid.length == 0) {
  4.             return 0;
  5.         }
  7.         int nr = grid.length;
  8.         int nc = grid[0].length;
  9.         int num_islands = 0;
  11.         for (int r = 0; r < nr; ++r) {
  12.             for (int c = 0; c < nc; ++c) {
  13.                 if (grid[r][c] == '1') {
  14.                     ++num_islands;
  15.                     grid[r][c] = '0';
  16.                     Queue<Integer> neighbors = new LinkedList<>();
  17.                     neighbors.add(r * nc + c);
  18.                     while (!neighbors.isEmpty()) {
  19.                         int id = neighbors.remove();
  20.                         int row = id / nc;
  21.                         int col = id % nc;
  22.                         if (row - 1 >= 0 && grid[row-1][col] == '1') {
  23.                             neighbors.add((row-1) * nc + col);
  24.                             grid[row-1][col] = '0';
  25.                         }
  26.                         if (row + 1 < nr && grid[row+1][col] == '1') {
  27.                             neighbors.add((row+1) * nc + col);
  28.                             grid[row+1][col] = '0';
  29.                         }
  30.                         if (col - 1 >= 0 && grid[row][col-1] == '1') {
  31.                             neighbors.add(row * nc + col-1);
  32.                             grid[row][col-1] = '0';
  33.                         }
  34.                         if (col + 1 < nc && grid[row][col+1] == '1') {
  35.                             neighbors.add(row * nc + col+1);
  36.                             grid[row][col+1] = '0';
  37.                         }
  38.                     }
  39.                 }
  40.             }
  41.         }
  43.         return num_islands;
  44.     }
  45. }

3、并查集

class Solution {
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int 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 numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc + c, (r-1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r+1][c] == '1') {
                        uf.union(r * nc + c, (r+1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c+1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }

        return uf.getCount();
    }
}