首页 > 其他 > 详细

Number of Islands

时间:2015-04-09 19:50:18      阅读:253      评论:0      收藏:0      [点我收藏+]

Given a 2d grid map of ‘1‘s (land) and ‘0‘s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

思路:宽度优先算法,碰到‘1‘没有被访问,则岛数++,同时该岛所有的‘1‘被标记为已访问。


public class Solution {
    LinkedList<int[]> q = new LinkedList<>();
    public int numIslands(char[][] grid) {
        if(grid==null){
            return 0;
        }
        int m=grid.length;
        if(m==0){
            return 0;
        }
        int n=grid[0].length;
        boolean[][] visited = new boolean[m][n];//标记(i,j)是否已被访问,这里仅标记'1',不标记'0'
        int cnt=0;//统计island的数目
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'&&visited[i][j]==false){//发现了新的island
                    bfs(grid,visited,i,j);//标记从该处'1'可达的所有'1'(即遍历整个岛屿)
                    cnt++;
                }
            }
        }
        return cnt;
    }
    private void bfs(char[][] grid, boolean[][] visited,int x,int y){
        fill(grid,visited,x,y);//先标记(x,y),再标记(x,y)的上下左右
        while(!q.isEmpty()){
            int[] point=q.poll();
            int i=point[0];
            int j=point[1];
            fill(grid,visited,i+1,j);
            fill(grid,visited,i-1,j);
            fill(grid,visited,i,j+1);
            fill(grid,visited,i,j-1);
        }
        
    }
    private void fill(char[][] grid, boolean[][] visited,int i,int j){
        if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!='1'||visited[i][j]==true){
            return;
        }
        visited[i][j]=true;
        q.add(new int[]{i,j});
    }
    
}

Number of Islands

原文:http://blog.csdn.net/u010786672/article/details/44963827

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!