题目主要信息:

  • 给定一个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,然后查询与之相邻的四个方向,看看能不能进入子问题。

图示如下: alt

代码实现:

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),其中mmnn为矩阵的长和宽,需要遍历整个矩阵,每次dfs搜索需要经过每个值为1的元素,但是最坏情况下也只是将整个矩阵变成0,因此相当于最坏遍历矩阵2次
  • 空间复杂度:O(nm)O(nm),最坏情况下整个矩阵都是1,递归栈深度为mnmn