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;
    }
}