200. Number of Islands

class Solution {
  void dfs(char[][] grid, int r, int c, boolean[][] seen) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0' || seen[r][c]) {
      return;
    }

    seen[r][c] = true;
    dfs(grid, r - 1, c, seen);
    dfs(grid, r + 1, c, seen);
    dfs(grid, r, c - 1, seen);
    dfs(grid, r, c + 1, seen);
  }

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

    int nr = grid.length;
    int nc = grid[0].length;
    boolean[][] seen = new boolean[nr][nc];
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1' && !seen[r][c]) {
          ++num_islands;
          dfs(grid, r, c, seen);
        }
      }
    }

    return num_islands;
  }
}

class Solution {
  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;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }

    return num_islands;
  }
}

class Solution {

    int[] par;

    public int numIslands(char[][] a) {
        if(a.length==0) return 0;

        int n = a.length, m=a[0].length;
        par = new int[m*n];
        Arrays.fill(par, -1);

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){

                if(a[i][j]=='1'){
                    par[i*m+j]=i*m+j; // note, that `par` was filled witn -1 values
                    if(i>0 && a[i-1][j]=='1') union(i*m+j, (i-1)*m+j); // union current+top
                    if(j>0 && a[i][j-1]=='1') union(i*m+j, i*m+(j-1)); // union current+left
                }

            }
        }

        Set<Integer> set = new HashSet<>();
        for(int k=0;k<par.length;k++){
            if(par[k]!=-1) set.add(find(k));
        }
        return set.size();
    }

    int find(int x){
        if(par[x]==x) return x;
        par[x]=find(par[x]);
        return par[x];
    }

    void union(int x, int y){
        int px = find(x);
        int py = find(y);
        par[px]=par[py];
    }

}