算法：100.岛屿数量

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

• 示例 1:

输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1

• 示例 2:

输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3

• 提示：

0. m == grid.length
1. n == grid[i].length
2. 1 <= m, n <= 300
3. grid[i][j] 的值为 '0' 或 '1'

题目分析

根据题意：我们要知道哪种算是岛屿，首先就是内部为1且周边是0，或者数组边界的1。

如何确定数组起点周边的情况呢？刚开始就想到用dfs去递归上下左右四个方向，然后递归我们都知道要有个跳出条件或者结束条件，对于本题，如果周边是0的话就不再递归，这样子便可结束；

然后岛屿数最开始数组种每个数都要开始去找，但是如果两个数相近，是不需要遍历的，我们dfs的时候，如果这个点找过，就置为0，因为找过的点，他就算在起点的那个岛上了，所以dfs要将找过的点置为0。

class Solution {
    public int numIslands(char[][] grid) {
        int num = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j] == '1'){
                    dfs(i,j,grid);
                    num++;
                }
            }
        }
        return num;
    }
​
    public void dfs(int i,int j,char[][] grid){
        grid[i][j] = 0;
        if(i-1 >=0 && grid[i-1][j] == '1'){
            dfs(i-1,j,grid);
        }
        if(i+1 <=grid.length-1 && grid[i+1][j] == '1'){
            dfs(i+1,j,grid);
        }
        if(j-1 >=0 && grid[i][j-1] == '1'){
            dfs(i,j-1,grid);
        }
        if(j+1 <=grid[i].length-1 && grid[i][j+1] == '1'){
            dfs(i,j+1,grid);
        }
    }
}
复制代码

官方有种通过广度优先进行检索

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
}
复制代码