题解 | #岛屿数量#

题目主要信息:

• 给定一个01矩阵，其中1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛
• 只考虑矩阵中上下左右为相邻，斜方不算相邻
• 求矩阵中表示的岛屿的个数

具体思路:

矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs），因此具体做法如下：

• step 1：优先判断空矩阵等情况。
• step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
• step 3：使用dfs将遍历矩阵遇到的1以及相邻的1全部置为0。

至于dfs具体怎么操作，我们接着看。当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，因此可以用递归实现。

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

图示如下：

代码实现:

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j) { //深度优先遍历与i，j相邻的所有1
        int n = grid.size();
        int m = grid[0].size();
        grid[i][j] = '0'; // 置为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++){
                if(grid[i][j] == '1'){ //遍历到1的情况
                    count++; //计数
                    dfs(grid, i, j); //将与这个1相邻的所有1置为0
                }
            }
        }
        return count;
    }
};

复杂度分析：

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