题解 | #岛屿数量#

#include <queue>
#include <vector>
struct point {
    int x;
    int y;
};
class Solution {
  public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */

    // 定义队列用于存放前置节点
    queue<pair<int, int>> pnt;
    point ps;
    int res = 0;
    // grid里面1表示有岛屿 0无 新增'-1'表示 已访问
    int solve(vector<vector<char> >& grid) {
        // write code here
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果岛屿已经访问过了或者无岛屿则跳过
                if (grid[i][j] == '#' || grid[i][j] == '0')
                    continue;
                res++;
                pnt.push({i, j});
                oneLoad(grid);
            }
        }
        return res;
    }
    // 通过打上标识，进行统计，这块内容类似于迷宫算法
    void oneLoad(vector<vector<char> >& grid) {
        int n = grid.size(), m = grid[0].size();
        // 使用广度优先遍历，类似树的层次遍历
        while (!pnt.empty()) {
            // 出队进行访问
            ps.x = pnt.front().first;
            ps.y = pnt.front().second;
            pnt.pop();
            int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
            //当前顶点的四个方向
            for (int i = 0; i < 4; i++) {
                point p;
                p.x = ps.x + dx[i];
                p.y = ps.y + dy[i];
                // 如果顶点越界则跳过
                if (p.x < 0 || p.x >= n || p.y < 0 || p.y >= m) continue;
                // 如果是陆地，则入队，设置为访问
                if (grid[p.x][p.y] != '#') {
                    if (grid[p.x][p.y] == '1')
                        pnt.push({p.x, p.y});
                    grid[p.x][p.y] = '#';
                }
            }
        }
    }
};