题解 | #岛屿数量#

class Solution {
  public:
//0跳，重复跳
    int dirt[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int count = 0;
        queue<pair<int, int>> que;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    que.push({i, j});
                    count++;//新岛屿数量加1
                    //bfs把岛屿相连部分去重
                    while (!que.empty()) {
                        auto tmp = que.front();
                        que.pop();
                        for (int k = 0; k < 4; k++) {
                            int nexti = tmp.first + dirt[k][0];
                            int nextj = tmp.second + dirt[k][1];
                            if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m &&
                                    grid[nexti][nextj] == '1') {
                                grid[nexti][nextj] = '0';
                                que.push({nexti, nextj}); //把一层的相关点压入
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};

dfs深度优先，遍历到1的时候分别往四个方向中一个合法方向下挖，到下一个点的时候依然重复下挖，表现深度优先，在遇到不合法情况则return回上一层合法点。所以，dfs以回溯的方式进行深度优先的遍历，加上已遍历过的情况记录，则为dp。

bfs广度优先，遍历到1的时候先把四个方向的合法点a先遍历，在遍历a的时候，用queue记录。此时，完成一层的遍历，并利用queue的记录，来开始下一层的遍历。