Given a 2d grid map of'1's (land) and'0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
class UnionFind{
private int[] father = null;
private int count;
public UnionFind(int n){
father = new int[n];
for(int i = 0; i < n; i ++){
father[i] = i;
}
}
private int find(int x){
if(father[x] == x)
return x;
return father[x] = find(father[x]);
}
public void connect(int x, int y){
int root_x = find(x);
int root_y = find(y);
if(root_x != root_y){
father[root_x] = root_y;//错很久，把一个root指向另一个root
count --;
}
}
public int query(){
return count;
}
public void set_count(int total){
count = total;
}
}
public class Solution {
int n, m;
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0)
return 0;
n = grid.length;
m = grid[0].length;
UnionFind uf = new UnionFind(n*m);
int total = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
if(grid[i][j] == '1'){
total ++; //一个点不能connect,只能计算total这里
}
}
}
uf.set_cou(total);
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
if(grid[i][j] == '1'){
for(int k = 0; k < 4; k ++){
int nx = i + dx[k];
int ny = j + dy[k];
if(isBound(grid, nx, ny)){
uf.connect(j + m * i, ny + m * nx);
}
}
}
}
}
return uf.query();
}
private boolean isBound(char[][] grid, int x, int y){
if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0')
return false;
return true;
}
}