```
/**
* two lands whose root-island is same refers to one island
* a root-island means thoese who point to themseves
*
* this method is used to find the root-island value of a island
*/
public class Solution {
public int numIslands(char[][] ch_grid) {
if(ch_grid.length<1){
return 0;
}
int height = ch_grid.length;
int width = ch_grid[0].length;
int[][] grid = new int[height][width];
for(int i=0;i<height;i++){
for(int j=0;j<width;j++){
if(ch_grid[i][j]=='1'){
grid[i][j] = 1;
continue;
}
///mark the water area with -100
grid[i][j] = -100;
}
}
int num =0;///num of island
for(int i=0;i<height;i++){
for(int j=0;j<width;j++){
if( grid[i][j]==-100){
continue;
}
int up = i>0 ? grid[i-1][j] : -1;
int left = j>0 ? grid[i][j-1] : -1 ;
int up_root = getRoot(up,width,grid);
int left_root = getRoot(left,width,grid);
up = up_root;
left = left_root;
if(up==left){
if(up<0){
grid[i][j] = i*width+j;//this is new island
++num;
continue;
}
//present land point to up
grid[i][j] = up;
}
if(up!=left){
if(up>=0&&left<0){
///up is lands ,but left not
//present land point to up
grid[i][j] = up;
}
if(up<0&&left<0){
///up is not lands ,and left neither
//this is a new island
grid[i][j] = i*width+j;
++num;
}
if(up<0&&left>=0){
///up is not lands ,but left is
grid[i][j] = left;
}
if(up>=0&&left>=0){
///up is lands ,and left too
//present land point to up
grid[i][j] = up;
///we have to combine the two islands into one
///left island point to up
grid[left/width][left%width] = up;
///reduce num
num--;
}
}
}
}
return num;
}
/**
* a root-island means thoese who point to themseves
*
* this method is used to find the root-island value of a island
*/
private int getRoot(int value,int width,int[][] grid){
if(value<0){
///this grid don't exist
return value;
}
int i = value/width;
int j = value%width;
if(grid[i][j]==value){
return value;
}
return getRoot(grid[i][j],width,grid);
}
}
```