题解 | #岛屿数量#

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个分支继续修改。

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    //深度优先遍历与i，j相邻的所有1
    void dfs(vector<vector<char> >& grid,int i,int j,int n,int m)
    {
        //将当前点置为0
        grid[i][j] = '0';
        //后续四个方向遍历
        if(i-1 >= 0 && grid[i-1][j] == '1')
            dfs(grid,i-1,j,n,m);
        if(i+1 < n && grid[i+1][j] == '1')
            dfs(grid,i+1,j,n,m);
        if(j-1 >= 0 && grid[i][j-1] == '1')
            dfs(grid,i,j-1,n,m);
        if(j+1 < m && grid[i][j+1] == '1')
            dfs(grid,i,j+1,n,m);
    }
    int solve(vector<vector<char> >& grid) {
        // write code here
        //判断空矩阵的情况
        if(grid.empty())
            return 0;
        int n = grid.size();
        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, n, m);
                }
            }
        }
        return count;
    }
};

2.广度优先搜索BFS

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

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

思路：

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

具体做法：

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

//BFS
#include <queue>
class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here
        //空矩阵的情况
        if(grid.empty())
            return 0;
        int n = grid.size();
        int m = grid[0].size();
        //记录岛屿数
        int count = 0;
        //遍历矩阵
        for(int i = 0;i<n;++i)
        {
            for(int j = 0;j<m;++j)
            {
                //遇到1要将这个1及与其相邻的1都置为0
                if(grid[i][j] == '1')
                {
                    //岛屿数增加
                    count++;
                    grid[i][j] = '0';
                    //记录后续bfs的坐标
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    //BFS
                    while(!q.empty())
                    {
                        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;

    }
};