题解 | #岛屿数量#

题目主要信息：

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛
只考虑上下左右为相邻
判断岛屿的个数

举一反三：

学习完本题的思路你可以解决如下题目：

方法一：dfs（推荐使用）

知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs）：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，因此可以用递归实现。

//后续四个方向遍历
if(i - 1 >= 0 && grid[i - 1][j] == '1') 
    dfs(grid, i - 1, j);
if(i + 1 < n && grid[i + 1][j] == '1') 
    dfs(grid, i + 1,j);
if(j - 1 >= 0 && grid[i][j - 1] == '1') 
    dfs(grid, i, j - 1);
if(j + 1 < m && grid[i][j + 1] == '1') 
    dfs(grid, i, j + 1);

终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。
返回值： 每一级的子问题就是把修改后的矩阵返回，因为其是函数引用，也不用管。
本级任务： 对于每一级任务就是将该位置的元素置为0，然后查询与之相邻的四个方向，看看能不能进入子问题。

具体做法：

step 1：优先判断空矩阵等情况。
step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
step 3：接着将该位置的1改为0，然后使用dfs判断四个方向是否为1，分别进入4个分支继续修改。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    //深度优先遍历与i，j相邻的所有1
    public void dfs(char[][] grid, int i, int j) { 
        int n = grid.length;
        int m = grid[0].length;
        // 置为0
        grid[i][j] = '0'; 
        //后续四个方向遍历
        if(i - 1 >= 0 && grid[i - 1][j] == '1') 
            dfs(grid, i - 1, j);
        if(i + 1 < n && grid[i + 1][j] == '1') 
            dfs(grid, i + 1,j);
        if(j - 1 >= 0 && grid[i][j - 1] == '1') 
            dfs(grid, i, j - 1);
        if(j + 1 < m && grid[i][j + 1] == '1') 
            dfs(grid, i, j + 1);
    }
    
    public int solve (char[][] grid) {
        int n = grid.length;
        //空矩阵的情况
        if (n == 0)  
            return 0;
        int m = grid[0].length;
        //记录岛屿数
        int count = 0; 
        //遍历矩阵
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < m; j++){
                //遍历到1的情况
                if(grid[i][j] == '1'){ 
                    //计数
                    count++; 
                    //将与这个1相邻的所有1置为0
                    dfs(grid, i, j); 
                }
            }
        }
        return count;
    }
}

C++实现代码：

class Solution {
public:
    //深度优先遍历与i，j相邻的所有1
    void dfs(vector<vector<char>>& grid, int i, int j) { 
        int n = grid.size();
        int m = grid[0].size();
        //置为0
        grid[i][j] = '0'; 
        //后续四个方向遍历
        if(i - 1 >= 0 && grid[i - 1][j] == '1') 
            dfs(grid, i - 1, j);
        if(i + 1 < n && grid[i + 1][j] == '1') 
            dfs(grid, i + 1,j);
        if(j - 1 >= 0 && grid[i][j - 1] == '1') 
            dfs(grid, i, j - 1);
        if(j + 1 < m && grid[i][j + 1] == '1') 
            dfs(grid, i, j + 1);
    }
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();
        //空矩阵的情况
        if (n == 0)  
            return 0;
        int m = grid[0].size();
        //记录岛屿数
        int count = 0; 
        //遍历矩阵
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < m; j++){
                //遍历到1的情况
                if(grid[i][j] == '1'){ 
                    //计数
                    count++; 
                    //将与这个1相邻的所有1置为0
                    dfs(grid, i, j); 
                }
            }
        }
        return count;
    }
};

Python实现代码：

class Solution:
    #深度优先遍历与i，j相邻的所有1
    def dfs(self, grid:List[List[chr]], i:int, j:int) : 
        n = len(grid)
        m = len(grid[0])
        #置为0
        grid[i][j] = '0' 
        #后续四个方向遍历
        if i - 1 >= 0 and grid[i - 1][j] == '1':
            self.dfs(grid, i - 1, j)
        if i + 1 < n and grid[i + 1][j] == '1':
            self.dfs(grid, i + 1, j)
        if j - 1 >= 0 and grid[i][j - 1] == '1':
            self.dfs(grid, i, j - 1)
        if j + 1 < m and grid[i][j + 1] == '1':
            self.dfs(grid, i, j + 1)
            
    def solve(self , grid: List[List[str]]) -> int:
        n = len(grid)
        #空矩阵的情况
        if  n == 0: 
            return 0
        m = len(grid[0])
        #记录岛屿数
        count = 0 
        #遍历矩阵
        for i in range(n): 
            for j in range(m):
                #遍历到1的情况
                if grid[i][j] == '1': 
                    #计数
                    count += 1 
                    #将与这个1相邻的所有1置为0
                    self.dfs(grid, i, j) 
        return count

复杂度分析：

时间复杂度： $O (n m)$ ，其中 $m$ 、 $n$ 为矩阵的长和宽，需要遍历整个矩阵，每次dfs搜索需要经过每个值为1的元素，但是最坏情况下也只是将整个矩阵变成0，因此相当于最坏遍历矩阵2次
空间复杂度： $O (n m)$ ，最坏情况下整个矩阵都是1，递归栈深度为 $m n$

方法二：bfs（扩展思路）

知识点：广度优先搜索（bfs）

广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再往更深处，进入与其他节点直接相连的节点。bfs的时候我们常常会借助队列的先进先出，因为从某个节点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再将与它们直接相连的节点加入，由此就可以依次按层访问。