Queue java solution.(For the case that a big map and a little island)


  • 0
    W
    public class Solution {
        public int islandPerimeter(int[][] grid) {
            int count = 0;
            int sum = 0;
            int height = grid.length;
            int width = grid[0].length;
    
            Queue<Integer> tmpQueue = new LinkedList<>();
    
            for(int i = 0 ; i < height ; i++) {
                for( int j = 0 ; j < width ; j++ ) {
                    if( grid[i][j] == 1) {
                        tmpQueue.offer(i);
                        tmpQueue.offer(j);
                        break;
                    }
                }
                if( tmpQueue.size() > 0) {
                    break;
                }
            }
    
            while(tmpQueue.size() > 0){
                
                int i = tmpQueue.poll();
                int j = tmpQueue.poll();
                
                if(grid[i][j] == -1)
                    continue;
                
                sum += 1;
                
                if( i > 0 ){
                    if(grid[i-1][j] == 1){
                        tmpQueue.offer(i-1);
                        tmpQueue.offer(j);
                        count += 1;
                    }
                }
                if( i < height -1 ){
                    if(grid[i+1][j] == 1){
                        tmpQueue.offer(i+1);
                        tmpQueue.offer(j);
                        count += 1;
                    }
                }
                if( j > 0 ){
                    if( grid[i][j-1] == 1){
                        tmpQueue.offer(i);
                        tmpQueue.offer(j-1);
                        count += 1;
                    }
                }
                if( j < width -1 ){
                    if( grid[i][j+1] == 1) {
                        tmpQueue.offer(i);
                        tmpQueue.offer(j+1);
                        count += 1;
                    }
                }
                
                grid[i][j] = -1;
                
            }
            
            return (sum*4)-(count*2);
    }
    

    We can change here to randomly method to find a island block.(If you know where maybe the island block in advance.)
    This is fit for the case that you get a big map and a little island.

            for(int i = 0 ; i < height ; i++) {
                for( int j = 0 ; j < width ; j++ ) {
                    if( grid[i][j] == 1) {
                        tmpQueue.offer(i);
                        tmpQueue.offer(j);
                        break;
                    }
                }
                if( tmpQueue.size() > 0) {
                    break;
                }
            }
    

Log in to reply
 

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