Given a boolean 2D matrix, 1 is represented as the sea, 0 is represented as the island. If two 0 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Examples

the given matrix is

0 0 0 1

1 0 1 1

1 1 0 0

0 1 0 0

there are 3 disjoint islands.

Solution 1: BFS, 每次遇到一个新的island，把周围相连的visited[i][j]设为true

  class Node {
    int x, y;
    public Node(int i, int j) {
      x = i;
      y = j;
    }
  }
  public int whiteObjects(int[][] matrix) {
    if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
        return 0;
    }
    int m = matrix.length, n = matrix[0].length, count = 0;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    boolean[][] visited = new boolean[m][n];
    Queue<Node> queue = new LinkedList<>();
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (!visited[i][j] && matrix[i][j] == 0) {
          count++;
          queue.offer(new Node(i, j));
          visited[i][j] = true;
          while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (int l = 0; l < 4; l++) {
                int x = cur.x + dx[l];
                int y = cur.y + dy[l];
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] == 0 && !visited[x][y]) {
                  queue.offer(new Node(x, y));
                  visited[x][y] = true;
                }
            }    
          }
        }
      }
    }  
    return count;
  }

Solution 2: Union Find, 检查与上下左右的点是否在同一个集合，如果不是，union, count--。二维转为一维的技巧

    public int numIslands(boolean[][] grid) {
        // Write your code here
        if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0){
            return 0;
        }

        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(m, n);
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int count = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == true){
                    int id1 = convert(i, j, n);
                    count++;
                    for(int k = 0; k < 4; k++){
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == true){
                            int id2 = convert(x, y, n);
                            if(uf.compressed_find(id1) != uf.compressed_find(id2)){
                                uf.union(id1, id2);
                                count--;
                            }
                        }
                    }
                }
            }
        }

        return count;

    }

    public int convert(int x, int y, int n){
            return x * n + y;
    }

    class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

            public UnionFind(int m, int n){
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        int id = convert(i, j, n);
                        father.put(id, id);
                    }
                }
            }

            public int compressed_find(int x){
                int parent = x;
                while(parent != father.get(parent)){
                    parent = father.get(parent);
                }
                int next;
                while(x != father.get(x)){
                    next = father.get(x);
                    father.put(x, parent);
                    x = next;
                }
                return parent;
            }

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                }
            }
    }