题目的主要信息：

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

方法一：dfs

具体做法：

可以从上到下从左到右依次遍历矩阵，每次遇到一个1则岛屿数记为1，然后将与这个1及与其相邻的所有1全部置为0，相当于这个岛屿已经被统计了，避免重复统计。

将邻近的1全部置为0的方法，我们可以用dfs。从每次遍历到的第一个1为起点，分别向四个方向进行深度优先搜索，注意不能越界且值为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$

方法二：bfs

具体做法：

统计岛屿的方法可以不变，但是将相邻的1全部置为0的方法还可以使用bfs。

利用队列辅助，每次队列进入第一个进入的1，然后遍历队列，依次探讨队首的四个方向，是否符合，如果符合则置为0，且位置坐标加入队列，继续遍历，直到队列为空。

class Solution {
public:
    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要将这个1及与其相邻的1都置为0
                    count++; //岛屿数增加
                    grid[i][j] = '0';
                    queue<pair<int, int>> q; //记录后续bfs的坐标
                    q.push({i, j}); 
                    while(!q.empty()){ //bfs
                        auto temp = q.front();
                        q.pop();
                        int row = temp.first;
                        int col = temp.second;
                        //四个方向依次检查：不越界且为1
                        if(row - 1 >= 0 && grid[row - 1][col] == '1'){
                            q.push({row - 1, col});
                            grid[row - 1][col] = '0';
                        }
                        if(row + 1 < n && grid[row + 1][col] == '1'){
                            q.push({row + 1, col});
                            grid[row + 1][col] = '0';
                        }
                        if(col - 1 >= 0 && grid[row][col - 1] == '1'){
                            q.push({row, col - 1});
                            grid[row][col - 1] = '0';
                        }
                        if(col + 1 < m && grid[row][col + 1] == '1'){
                            q.push({row, col + 1});
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }
        return count;
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，其中$mm$、$nn$为矩阵的长和宽，需要遍历整个矩阵，每次bfs搜索需要经过每个值为1的元素，但是最坏情况下也只是将整个矩阵变成0，因此相当于最坏遍历矩阵2次
• 空间复杂度：$(min(n,m))(min(n,m))$，bfs最坏情况队列大小为长和宽的较小值