LeetCode200. 島嶼的個數

給定一個由 

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