题解 | #岛屿数量#

方法一：DFS（深度优先搜索）

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

使用深度优先搜索（dfs）：遍历矩阵，当遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，可以用递归实现。这样就将一个岛全部置0了。继续向下遍历矩阵重新进入上述的case。

时间复杂度：o(nm)。n、m为矩阵的行数和列数

空间复杂度：o(nm)。n、m为矩阵的行数和列数

class Solution {
public:
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();     //行数
        int m = grid[0].size();  //列数
		//特殊情况处理（空矩阵）
        if(n == 0)
            return 0;
        
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    count++;
					//广度优先搜索
                    dfs(grid, i, j, n, m);
                }
            }
        }

        return count;
    }
private:
    void dfs(vector<vector<char> >& grid, int row, int col, int maxRow, int maxCol) {
        grid[row][col] = '0';
        //上方
        if(grid[row - 1][col] == '1' && row > 0)
            dfs(grid, row - 1, col, maxRow, maxCol);
        //下方
        if(grid[row + 1][col] == '1' && row + 1 < maxRow)
            dfs(grid, row + 1, col, maxRow, maxCol);
        //左侧
        if(grid[row][col - 1] == '1' && col > 0)
            dfs(grid, row, col - 1, maxRow, maxCol);
        //右侧
        if(grid[row][col + 1] == '1' && col + 1 < maxCol)
            dfs(grid, row, col + 1, maxRow, maxCol);
        
        return;
    }
};

方法二：BFS（广度优先搜索）

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

思路：

统计岛屿的方法可以和方法一同样遍历解决，为了去重我们还是要将所有相邻的1一起改成0，这时候同样遍历连通的广度优先搜索（bfs）可以代替dfs。

具体做法：

• step 1：优先判断空矩阵等情况。
• step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
• step 3：使用bfs将遍历矩阵遇到的1以及相邻的1全部置为0：利用两个队列辅助（C++可以使用pair），每次队列进入第一个进入的1，然后遍历队列，依次探讨队首的四个方向，是否符合，如果符合则置为0，且位置坐标加入队列，继续遍历，直到队列为空。

时间复杂度：o(nm)。n、m为矩阵的行数和列数

空间复杂度：o(nm)。n、m为矩阵的行数和列数

class Solution {
  public:
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();     //行数
        int m = grid[0].size();  //列数
		//特殊情况处理（空矩阵）
        if (n == 0)
            return 0;

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    pos_x.push(i);
                    pos_y.push(j);
                    grid[i][j] = '0';
                    // 广度优先搜索
                    while (!pos_x.empty() && !pos_y.empty()) {
                        int length = pos_x.size();
                        for (int i = 0; i < length; i++) {
                            int row = pos_x.front();
                            pos_x.pop();
                            int col = pos_y.front();
                            pos_y.pop();
                            //上方
                            if (grid[row - 1][col] == '1' && row > 0) {
                                pos_x.push(row - 1);
                                pos_y.push(col);
                                grid[row - 1][col] = '0';
                            }
                            //下方
                            if (grid[row + 1][col] == '1' && row + 1 < n) {
                                pos_x.push(row + 1);
                                pos_y.push(col);
                                grid[row + 1][col] = '0';
                            }
                            //左侧
                            if (grid[row][col - 1] == '1' && col > 0) {
                                pos_x.push(row);
                                pos_y.push(col - 1);
                                grid[row][col - 1] = '0';
                            }
                            //右侧
                            if (grid[row][col + 1] == '1' && col + 1 < m) {
                                pos_x.push(row);
                                pos_y.push(col + 1);
                                grid[row][col + 1] = '0';
                            }
                        }
                    }
                }
            }
        }

        return count;
    }
  private:
    queue<int> pos_x;
    queue<int> pos_y;
};