BFS

宽搜算法

    BFS适用于“知道初始状态、最终状态，要求与过程路径的相关解”的题目。

核心剖解

    宽搜借助队列实现，类似于树结构的节点遍历。

    从根节点开始，对每一个使用点都要在其父节点的循环中进行入队、设置访问vis[]操作（根节点的初始化要在循环外进行），检查当前节点的子节点中是否有退出点，有则终止遍历，没有就把子节点入队、设置访问。

    对于一些需要记录过程状态的题目，还需要用另一个数组dis[]来进行状态转移。

bool vis[];
type dis[]; // 状态转移数组
inline bool isValid(node& v) { } // 边界检查函数
int bfs() {
    queue q;
    node vc, vn;
    q.emplace(vc);
    vis[vc.x][vc.y] = 1;
    while (!q.empty()) {
        vc = q.front();
        q.pop();
        for (/*any rule*/) {
            vn.x = vc.x+……; // 按规则寻找子节点
            vn.y = vc.y+……;
            if (isValid(vn) && !vis[vn.x][vn.y]) { // 子节点入队、访问
                q.emplace(vn);
                vis[vn.x][vn.y] = 1;
                dis[vn.x][vn.y] = dis[vc.x][vc.y] + 1; // 记录状态
            }
            if (vn==ed) return dis[ed.x][ed.y];
        }
    }
    return -1; // 无结果
}