200.Number of Islands

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

题目大意

1表示陆地块，0表示水域块，计算由陆地块构成的岛的个数，这里的岛只能通过相邻水平和垂直方向的路地块构成。

解题思路

调用bfs或者dfs的来计算连通数，这里的连通数就是岛屿个数

AC代码

bfs:

class Solution {
      public static class Point{
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int x;
        public int y;
    }
    int dep[][]=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};  //方向数组
    public void bfs(char[][] grid,int x,int y){
        grid[x][y]='0'; //遍历过后将该陆地块标记为0
        Queue<Point> queue=new LinkedList<>();
        Point parent=new Point(x,y);
        queue.add(parent);
        while(!queue.isEmpty()){
            Point current=queue.remove();
           
            for (int i = 0; i <dep.length ; i++) {
                int nx=current.x+dep[i][0];
                int ny=current.y+dep[i][1];
                if(nx>=0&&nx<grid.length&&ny>=0&&ny<grid[0].length&&grid[nx][ny]=='1'){ //检查边界以及状态
                    Point nc=new Point(nx,ny);
                    queue.add(nc);
                    grid[nx][ny]='0'; //添加队列后，标记该陆地块为0，表示已遍历过

                }

            }
        }

    }
    public int numIslands(char[][] grid) {
        int num=0;
        for (int i = 0; i <grid.length; i++) {
            for (int j = 0; j <grid[0].length ; j++) {
                if(grid[i][j]=='1') {
                    num++;
                    bfs(grid, i, j);
                }
            }
        }
        return num;
    }
}