Simpe Java Solution handling all cases Greedy Algorithm


  • 0
    G

    ...
    package dec;

    public class IslandPerimeter {

    public static void main(String g[]) {
    	IslandPerimeter ip = new IslandPerimeter();
    	//int [][] value ={{0,1,0,0},{1,1,1,0}, {0,1,0,0}, {1,1,0,0}};
    	int [][] value ={{1},{1}};
    	ip.islandPerimeter(value);
    }
    
    public int islandPerimeter(int[][] grid) {
    	int perimeter = 0;
    	boolean changeHua = false;
    	for (int i=0;i<grid.length;i++) {
    		for(int j=0;j<grid[i].length;j++) {
    			if (grid[i][j]==1 && perimeter==0) {
    				perimeter+=4;
    			}
    			else {
    				changeHua=false;
    
    				
    				// check if left entry is possible
    				if( j>=1 &&  i>=1   && grid[i-1][j]==1 && grid[i][j-1]==0 && grid[i][j]==1) {
    					perimeter+=2;
    					changeHua=true;
    				}
    				
    				// top and left both are 1
    				if( i-1>=0  && j-1>=0 && grid[i-1][j]==1 && grid[i][j-1]==1 && grid[i][j]==1) {
    					continue;
    				}
    				
    				// check if top entry is possible and left is 0
    				 if( j-1>=0 && i-1>=0 && grid[i][j-1]==1 &&  grid[i][j]==1 &&  grid[i-1][j]==0) {
    					perimeter+=2;
    					changeHua=true;
    					continue;
    					
    				}
    			
    
     				
    				 if( j-1>=0 && grid[i][j-1]==0 &&   grid[i][j]==1 && !changeHua) {
    					 perimeter+=4;
    					 changeHua=true;
    					 continue;    				
    				}    				 
    				 // case when item is in 1st row and left is 1
    				 if( j-1>=0 && grid[i][j-1]==1 &&   grid[i][j]==1 && !changeHua) {
    					 perimeter+=2;
    					 changeHua=true;
    					 continue;    				
    				} 
    				 
    				 // case when item is in 1st column and top is 1
    				 if( i-1>=0 && grid[i-1][j]==1 &&   grid[i][j]==1 && !changeHua) {
    					 perimeter+=2;
    					 changeHua=true;
    					 continue;    				
    				} 	 
    				 
    				 if( i-1>=0   && grid[i-1][j]==0 && grid[i][j]==1 && !changeHua) {
     					changeHua=true;
    					perimeter+=4;
    					 continue;
    					
    				}    				 
    				 
    			}
    		}//for
    	}//for
    	System.out.println(perimeter);
        return perimeter;
    }
    

    }

    ...


Log in to reply
 

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