LeetCode 200. 島嶼數量（Java）

1. 島嶼數量

給定一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，計算島嶼的數量。一個島被水包圍，并且它是通過水準方向或垂直方向上相鄰的陸地連接配接而成的。你可以假設網格的四個邊均被水包圍。

示例 1:

輸入:

11110

11010

11000

00000

輸出: 1

示例 2:

輸入:

11000

11000

00100

00011

輸出: 3

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/number-of-islands

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

判斷方式：隻要連在一起的島嶼就都算一個

方法一：廣度優先搜尋BFS

class Solution {
//
    class Point{
        int x;
        int y;
        public  Point(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1) {
            return 0;
        }
        int count = 0;
        int len1 = grid.length;
        int[] moveX = {-1, 1, 0, 0};
        int[] moveY = {0, 0, -1, 1};
        //建立隊列
        LinkedList<Point> queue = new LinkedList();
        for (int i = 0; i < len1 ; i++) 
        {
            int len2 = grid[i].length;
             for (int j = 0; j < len2; j++) 
             {
                 if (grid[i][j] == '1') {//如果為島嶼
                    count++;
                    grid[i][j] = '0';
                    queue.add(new Point(i, j));//則加入隊列
                    // 廣度優先周遊，上下左右染色
                     while (queue.size() != 0)  //如果隊列不為空
                     {
                         Point p = queue.poll();//從隊中取一個元素
                         //取其上下左右的元素進行判斷
                         for (int k = 0; k < moveX.length; k++) 
                         {
                             int x = p.x + moveX[k];
                             int y = p.y + moveY[k];
                             if (isValid(len1, len2, x, y) && grid[x][y] == '1') //如果新節點沒有越界且為1
                             {
                                 grid[x][y] = '0';//将周遊過的設為0
                                 queue.add(new Point(x, y));//并将新節點添加到隊列中
                             }
                         }
                     }
                 }
             }
        }
        return count;
    }
    //判斷是否越界
    private boolean isValid(int len1,int len2, int x, int y) {
        return x >= 0 && x < len1 && y >= 0 && y < len2;
    }
}
           

方法二：DFS深度優先搜尋，遞歸查詢

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0)
        {
            return 0;
        }
        int len1=grid.length;
        int len2=grid[0].length;
        int count=0;
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                if(grid[i][j]=='1')
                {
                    count++;
                    DFS(grid,i,j);
                }
            }
        }
        return count;
    }
    public void DFS(char[][] grid,int a,int b)
    {
        int len1=grid.length;
        int len2=grid[0].length;
        if(a<0||b<0||a>=len1||b>=len2||grid[a][b]=='0')
        {
            return;
        }
        grid[a][b]='0';
        DFS(grid,a-1,b);
        DFS(grid,a+1,b);
        DFS(grid,a,b-1);
        DFS(grid,a,b+1);
    }
}