Detail noted java answer


  • 0
    N
     /**
                 * 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);
        	    }
        	    
            
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.