题目描述

注意，需要求的是岛屿的数量，而不是岛屿的总面积，
这道题很考验对dfs思路的理解，而不是简单地套用模版。
可以用dfs和bfs两种方法做。

深度优先搜索版本

首先看代码：

class Solution {
private:
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的

                visited[nextx][nexty] = true; 
                dfs(grid, visited, nextx, nexty);
            } 
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); 

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') { 
                    visited[i][j] = true;
                    result++; // 遇到没访问过的陆地，+1
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
};

这个代码的思路是：在numIslands函数里，通过循环每次找到一个没有被访问过的岛屿。在新岛屿上找到一个起始点后，用dfs对这个岛屿上所有的陆地点标记为visited，然后再回到numIslands函数里寻找下一个新岛屿（这里就能看出dfs操作的作用）。
但是看代码后会发现，这个dfs和一般的dfs代码很不一样，因为在开头没有终止条件。理解这里就需要对dfs或者回溯算法的执行过程细节熟悉。
在前面学习的回溯算法里，需要注意，return语句并不是为了“停止遍历”，而是为了“在合适的位置停止遍历”，其实就算不加return语句，许多回溯函数在遍历所有可能结果后也会自动停止并回溯，因为运行到边界后，程序不会进入for循环而是直接运行到函数结尾，这个过程其实和return ;的效果是一样的，只有在：遍历已经到达尽头，但是仍然会进入下一层递归的情况下，才有可能造成死循环。所以控制递归调用的位置才是避免死循环的关键。
所以在这个代码里，由于dfs函数只会遍历陆地方块，所以不需要return语句，它自然地就会遍历一个岛屿的所有陆地然后结束。

广度优先搜索版本

根据上面的算法，广度优先版本的思路就很容易想到，也是在numIslands里寻找新的岛屿，在bfs函数里遍历整个岛屿的所有陆地。
代码如下：

class Solution {
private:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited[x][y] = true; // 只要加入队列，立刻标记
    while(!que.empty()) {
        pair<int ,int> cur = que.front(); que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                que.push({nextx, nexty});
                visited[nextx][nexty] = true; // 只要加入队列立刻标记
            }
        }
    }
}
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    result++; // 遇到没访问过的陆地，+1
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
};

可以看出，bfs中没有用到递归，而是通过循环实现的。
通过que.push({nextx, nexty});语句，每次将后续结点入队，直到que.empty()，即没有任何后继结点，也就是所有结点都被遍历过，这时结束循环。

一种可能出现的错误：