LeetCode200. 岛屿的个数

Bertha 。 2022-05-09 09:03 105阅读 0赞

给定一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

**示例 1:**

输入:
    11110
    11010
    11000
    00000
    
    输出: 1

**示例 2:**

输入:
    11000
    11000
    00100
    00011
    
    输出: 3

--------------------

思路：当发现一个岛屿时，与其上下左右相邻的岛屿都算作同一个岛屿，同样新加入的岛屿的上下左右相邻的岛屿也都算作同一个岛屿，以后再遍历到这些岛屿都不予计数。

class Solution {
        public int numIslands(char[][] grid) {
             if(null==grid||grid.length==0){
                return 0;
            }
             boolean[][] used=new boolean[grid.length][grid[0].length];//该岛屿是否已经遍历
            ArrayDeque<Index> queue=new ArrayDeque<Index>();
            int count=0;//岛屿数
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    if(grid[i][j]=='1'&&used[i][j]==false){
                        Index tmp=new Index(i,j);
                        count++;
                        queue.add(tmp);
                        while (!queue.isEmpty()){
                            Index index=queue.removeFirst();
                            if(index.x<grid.length-1){//判断右边是否是岛屿
                                if(grid[index.x+1][index.y]=='1'&&used[index.x+1][index.y]==false){
                                    queue.add(new Index(index.x+1,index.y));
                                    used[index.x+1][index.y]=true;
                                }
                            }
                            if(index.y<grid[0].length-1){//判断下边是否有岛屿
                                if(grid[index.x][index.y+1]=='1'&&used[index.x][index.y+1]==false){
                                    queue.add(new Index(index.x,index.y+1));
                                    used[index.x][index.y+1]=true;
                                }
                            }
                             if(index.y>0){//判断左边是否有岛屿
                                if(grid[index.x][index.y-1]=='1'&&used[index.x][index.y-1]==false){
                                    queue.add(new Index(index.x,index.y-1));
                                    used[index.x][index.y-1]=true;
                                }
                            }
                             if(index.x>0){//判断上边是否有岛屿
                                if(grid[index.x-1][index.y]=='1'&&used[index.x-1][index.y]==false){
                                    queue.add(new Index(index.x-1,index.y));
                                    used[index.x-1][index.y]=true;
                                }
                            }
                        }
                    }
                }
            }
            return count;
        }
        
         public  class Index{
            int x;//行索引
            int y;//列索引
    
            public Index(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    }