BFS commented Java Solution


  • 0
    U
    public class Solution {//islands keep the information of how many islands are and elment of each island, for this question, we only need return islands.size();
    /*
    for each grid[i][j]==1&&grid[i][j] do not belong to any islands explored. 
    do bfs find all surrounding '1'that can contribute to an island, 
    add the island to list islands.
    */
    public int numIslands(char[][] grid) {
        if(grid.length==0||grid[0].length==0)
            return 0;
            
        List<List<Point>> islands= new ArrayList<List<Point>>();
        int m=grid.length,n=grid[0].length;
        boolean[][] inSomeIsland= new boolean[m][n];
        int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
        for(int i=0;i<m;i++){
            for(int j=0; j<n;j++){
                if(grid[i][j]=='1'&&!inSomeIsland[i][j]){
                    Queue<Point> queue = new LinkedList<>();
                    List<Point> island= new ArrayList<Point>();
                    queue.add(new Point(i, j));
                    inSomeIsland[i][j]=true;
                    island.add(new Point(i,j));
                    while (!queue.isEmpty()) {
                        Point point = queue.poll();
                        for (int k = 0; k < 4; k++) {
                            int x = direction[k][0] + point.x;
                            int y = direction[k][1] + point.y;
                            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1'&&!inSomeIsland[x][y]) {
                                island.add(new Point(x,y));
                                inSomeIsland[x][y]=true;
                                queue.add(new Point(x, y));
                            }
                        }
                    }
                    if(island.size()>0)
                        islands.add(island);    
                }    
            }
        }
        
        return islands.size(); 
        
        }
    
    }
    class Point {
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    }

Log in to reply
 

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