@Dmaxiya 2020-08-25T00:40:07.000000Z 字数 11537 阅读 1344

广度优先搜索

Hello_World

bfs

广度优先搜索 $(Breadth-first~search)$ 简称 $bfs$ ，它的搜法是对于当前状态，依次搜索其后继状态，其后继状态都搜索结束后，再搜索这些后继状态所产生的更多的后继状态，从搜索树的角度来看，就是搜索同一深度的所有状态，再搜索下一深度的所有状态。
对于下面这棵树，宽搜的顺序就是按 $A~B~C\cdots\cdots$ 的字母表顺序。

下面这张图从 $B$ 点开始的宽搜顺序为：

$B\rightarrow A[B]\rightarrow D[B]\rightarrow F[A]\rightarrow C[A]\rightarrow(C[D])\rightarrow E[C]\rightarrow H[E]\rightarrow G[H]\rightarrow J[H]\rightarrow I[G]\rightarrow(I[J])$
中括号的节点表示搜索到当前节点的前一节点编号，小括号中的节点表示本应该搜索到当前节点，但由于之前已经搜索过，所以应当跳过搜索。

bfs 思路

从上面的搜索次序可以大概这样理解图上 $bfs$ ：从某个点开始一层一层地往外搜索节点，直到所有节点都被搜索到。在上图的搜索过程中，搜索到节点 $A$ 时，不再继续往下搜索，而是先存起来，等到 $D$ 搜索结束后再开始 $A$ 的搜索。
看到这里我们可以用一个二维数组 $node[i][j]$ 表示从初始节点开始，搜索到第 $i$ 层时的第 $j$ 个节点（把“层”这个字放在树上会不会更好理解一些？），在搜索到第 $i+1$ 层时，在第 $i$ 层的一维数组上跑一个 $for$ 循环即可。但是二维数组的需要的空间太大，如果真的要用二维数组来实现宽搜，空间复杂度为 $O(n^2)$ ，其中 $n$ 为节点数。
进一步观察我们可以发现，第 $i+1$ 层的搜索次序只依赖于第 $i$ 层的搜索，而完全用不到第 $i$ 层之前的搜索数据，所以我们可以将这么大的一个二维数组用一个滚动数组代替，即将第 $i$ 层的搜索结果储存在第 $i\%2$ 行的一维数组中，而第 $i+1$ 层的搜索就可以通过对第 $i\%2$ 行的一维数组进行一次 $for$ 循环。这样的空间复杂度就可以下降到 $O(2n)$ ，已经是足够优化的空间了，只是实现起来由于宽搜搜索层数的不确定，不好给出“跳出循环”或者“结束递归” 的条件（取决于你用哪种方法实现）。

继续观察这个滚动数组 $for$ 循环的次序可以发现，这个次序总是按顺序在两个数组中从左到右依次扫描，对于第 $i$ 行的一维数组，当我们扫描到第 $j$ 个节点时，会将第 $j$ 个节点的所有没有被访问过的后继节点都放入到第 $(i+1)\%2$ 行一维数组的末尾，接着第 $j$ 个节点就不会被扫描到，而是继续扫描第 $j+1$ 个节点，直到第 $i$ 行的所有节点都被扫描到，进而继续扫描第 $(i+1)\%2$ 行的节点。
我们能否将这两个一维数组拼接起来，仅用一维来实现呢？以上的扫描次序和添加待扫描节点的次序正好符合“先进先出”的规律，所以这一维数组也就可以转化为一个队列，用一个队列来存放待扫描的所有节点，如果队首的节点所有后继节点已经被存入队列，则这个节点就已经失去了作用，可以从队列中剔除，并且不再需要它。

将本小结“节点”的含义替换成“状态”，将“图”替换成“解空间”，同样成立。

bfs 代码实现

queue<Node> que;
bool vis[maxn];
que.push(s);
vis[s] = true;
while(!que.empty()) {
    Node tmp = que.front();
    que.pop();
    /*对 tmp 节点的相关操作*/
    int len = G[tmp.pos].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[tmp.pos][i].pos;
        if(!vis[pos] && (/*其他能够进入队列的条件*/)) {
            /*对 pos 节点的相关操作*/
            vis[pos] = true;
            que.push(pos);
        }
    }
}

如果由于某些条件必须跳出循环，则可以在第 $9$ 行加入一个判断语句然后 $break$ ，并且需要在第 $3$ 行加入清空队列的初始化：

while(!que.empty()) {
    que.pop();
}

关于队列的相关函数的作用和意义，请下载群文件“ $OJ$ 提交 $\&$ $STL$ 基础”自学 $STL$ 相关内容，假期不再布置 $STL$ 相关习题。

bfs 应用

在边权相等情况下搜索从一个点到达图上其他所有点的最短路径；由于边权相同，所以到达 $x$ 节点的时间等于到达 $x$ 节点的宽搜层数，第一次搜索到节点 $x$ 的层数必然是最小层数，所以第一次搜索到节点 $x$ 的路径就是到达节点 $x$ 的最短路径。
拓扑排序；拓扑排序的宽搜写法比较容易实现与理解（还有深搜的写法），但是注意拓扑排序初始进入队列的不是一个点，而是所有入度为零的点。
迪杰斯特拉最短路；迪杰斯特拉最短路算法的堆优化（将队列改为优先队列）写法时间复杂度为 $O(m\log m)$ ，其中 $m$ 为图上边的数量，对于完全图（ $n^2$ 条边）的时间复杂度为 $O(n^2\log n^2)$ ，效率不如 $dij$ 的朴素写法（ $O(n^2)$ ）。
$prim$ 最小生成树； $prim$ 最小生成树算法的堆优化时间复杂度为 $O(m\log m)$ ，完全图的情况和 $dij$ 相同，此时最好直接用 $prim$ 的朴素写法 $O(n^2)$ 。
$bfs$ 序：目前看到用到 $bfs$ 序的好像只有“ $AC$ 自动机”算法，这个是 $Trie$ 字典树上跑 $KMP$ 的一种多字符串匹配的算法，若是涉及到 $AC$ 自动机的话比较常用，蓝桥杯一般不考，可以不用理解。

2 月 13~14 日 bfs 练习题解

A. Knight Moves

题意

在一个 $l\times l$ 的方格中，走“日”字步从 $(s_x,s_y)$ 点走到 $(t_x,t_y)$ 点，问最少走多少步。

数据范围

$4\leq l\leq300\\0\leq s_x,s_y,t_x,t_y<l$

题解

从 $(s_x,s_y)$ 点开始 $bfs$ ，第一次搜索到达的点用的步数一定是最少的，所以只要记录第一次到达每个点的步数，后面若重复搜索到这个点，则不再进入队列，最后输出到达 $(t_x,t_y)$ 的步数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 500;
struct Node {
    int x, y;
    Node() {}
    Node(int xx, int yy) {
        x = xx;
        y = yy;
    }
};
bool operator==(const Node &a, const Node &b) {
    return a.x == b.x && a.y == b.y;
}
int T, n;
Node s, t;
int step[maxn][maxn];
queue<Node> que;
const int dir[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {1, 2}, {2, 1}};
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
int bfs() {
    while(!que.empty()) {
        que.pop();
    }
    memset(step, -1, sizeof(step));
    que.push(s);
    step[s.x][s.y] = 0;
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        if(tmp == t) {
            break;
        }
        for(int i = 0; i < 8; ++i) {
            int xx = tmp.x + dir[i][0];
            int yy = tmp.y + dir[i][1];
            if(in(xx, yy) && step[xx][yy] == -1) {
                step[xx][yy] = step[tmp.x][tmp.y] + 1;
                que.push(Node(xx, yy));
            }
        }
    }
    return step[t.x][t.y];
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        scanf("%d%d%d%d", &s.x, &s.y, &t.x, &t.y);
        printf("%d\n", bfs());
    }
    return 0;
}

B. Catch That Cow

题意

在一个一维坐标轴上， $John$ 最初在 $x=N$ 点，他的牛跑到了 $x=K$ 点，牛在 $x=K$ 点不动，若他在点 $x$ ，则他下一步可以移动到 $x-1$ 、 $x+1$ 、 $2\times x$ 这三个位置，问他最快多久能找到牛。

数据范围

$0\leq N,K\leq10^5$

题解

从 $x=N$ 点开始 $bfs$ ，思路同上，但是注意农夫可以走的范围实际上是 $[0,1.5\times10^5)$ ，所以要注意数组的大小，否则很可能会 $RE$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, k;
int step[maxn];
int Set[maxn], cnt;
queue<int> que;
void Change(int Index, int x) {
    Set[cnt++] = Index;
    step[Index] = x;
}
void Clear() {
    for(int i = 0; i < cnt; ++i) {
        step[Set[i]] = -1;
    }
    cnt = 0;
}
bool in(int x) {
    return x >= 0 && x < maxn;
}
int bfs() {
    while(!que.empty()) {
        que.pop();
    }
    que.push(n);
    Change(n, 0);
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        if(tmp == k) {
            break;
        }
        if(in(tmp - 1) && step[tmp - 1] == -1) {
            Change(tmp - 1, step[tmp] + 1);
            que.push(tmp - 1);
        }
        if(in(tmp + 1) && step[tmp + 1] == -1) {
            Change(tmp + 1, step[tmp] + 1);
            que.push(tmp + 1);
        }
        if(in(tmp * 2) && step[tmp * 2] == -1) {
            Change(tmp * 2, step[tmp] + 1);
            que.push(tmp * 2);
        }
    }
    return step[k];
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    memset(step, -1, sizeof(step));
    while(scanf("%d%d", &n, &k) != EOF) {
        Clear();
        printf("%d\n", bfs());
    }
    return 0;
}

C. Dating with girls(2)

题意

你想和一个女生约会，你和这个女生都在一个 $r\times c$ 的迷宫当中，这个迷宫中的石头将会在 $x\times k(x\in N)$ 的时间点消失，其他时候它们都将在那里。要从 $Y$ 的位置走到 $G$ 的位置，问最少需要多少分钟。

数据范围

$1\leq r,c\leq100,2\leq k\leq10$

题解

石头会在 $k$ 的整数倍的时间点消失，所以整个搜索的周期不是 $1$ 而是 $k$ ，如果周期为 $1$ 就是前面两道题的宽搜，周期为 $k$ 就多开一维表示某个周期中的第 $t(t\in[0,k-1])$ 个时间点到达某个点的最短时间。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
struct Node {
    int x, y;
    int k;
    Node() {}
    Node(int xx, int yy, int kk) {
        x = xx;
        y = yy;
        k = kk;
    }
};
bool operator==(const Node &a, const Node &b) {
    return a.x == b.x && a.y == b.y;
}
int T, n, m, k;
Node s, t;
queue<Node> que;
char str[maxn][maxn];
int step[maxn][maxn][15];
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
    while(!que.empty()) {
        que.pop();
    }
    memset(step, -1, sizeof(step));
    step[s.x][s.y][s.k] = 0;
    que.push(s);
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        if(tmp == t) {
            return step[tmp.x][tmp.y][tmp.k];
        }
        int St = step[tmp.x][tmp.y][tmp.k] + 1;
        for(int i = 0; i < 4; ++i) {
            int xx = tmp.x + dir[i][0];
            int yy = tmp.y + dir[i][1];
            if(in(xx, yy) && step[xx][yy][St % k] == -1 && (St % k == 0 || str[xx][yy] != '#')) {
                step[xx][yy][St % k] = St;
                que.push(Node(xx, yy, St % k));
            }
        }
    }
    return -1;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i < n; ++i) {
            scanf("%s", str[i]);
            for(int j = 0; j < m; ++j) {
                if(str[i][j] == 'Y') {
                    s.x = i;
                    s.y = j;
                    s.k = 0;
                } else if(str[i][j] == 'G') {
                    t.x = i;
                    t.y = j;
                }
            }
        }
        int ans = bfs();
        if(ans == -1) {
            printf("Please give me another chance!\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

2月15日 bfs 练习题解

A. Nightmare

题意

在一个 $N\times M$ 的迷宫中， $Ignatius$ 手里拿着一个定时炸弹，最初倒计时设为 $6$ 分钟，他可以在迷宫中上下左右移动，每移动一格耗时 $1$ 分钟，在迷宫的某些地方设有重置器，可以将定时炸弹的时间重置为 $6$ 分钟。如果定时器倒计时到 $0$ ，不论走到哪一格，炸弹都将爆炸，问他能否安全到达出口，如果可以，最短需要多长时间。

数据范围

$1\leq N,M\leq8$

题解

和 Dating with girls(2) 题一样，多开一维表示炸弹倒计时为 $t$ 时，到达某一格的最短时间，到达某一格时，若倒计时为 $1$ 且这一格不是出口，则不再搜索。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 20;
struct Node {
    int x, y;
    int Time;
    Node() {}
    Node(int xx, int yy, int t) {
        x = xx;
        y = yy;
        Time = t;
    }
};
bool operator==(const Node &a, const Node &b) {
    return a.x == b.x && a.y == b.y;
}
int T, n, m;
Node s, t;
queue<Node> que;
int step[maxn][maxn][10];
int num[maxn][maxn];
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
    while(!que.empty()) {
        que.pop();
    }
    memset(step, -1, sizeof(step));
    step[s.x][s.y][s.Time] = 0;
    que.push(s);
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        if(tmp == t) {
            return step[tmp.x][tmp.y][tmp.Time];
        }
        if(tmp.Time == 1) {
            continue;
        }
        for(int i = 0; i < 4; ++i) {
            int xx = tmp.x + dir[i][0];
            int yy = tmp.y + dir[i][1];
            int Time = tmp.Time - 1;
            if(in(xx, yy) && num[xx][yy] != 0) {
                if(num[xx][yy] == 4) {
                    Time = 6;
                }
                if(step[xx][yy][Time] == -1) {
                    step[xx][yy][Time] = step[tmp.x][tmp.y][tmp.Time] + 1;
                    que.push(Node(xx, yy, Time));
                }
            }
        }
    }
    return -1;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                scanf("%d", &num[i][j]);
                if(num[i][j] == 2) {
                    s.x = i;
                    s.y = j;
                    s.Time = 6;
                } else if(num[i][j] == 3) {
                    t.x = i;
                    t.y = j;
                }
            }
        }
        printf("%d\n", bfs());
    }
    return 0;
}

B. 诡异的楼梯

题解

到达楼梯时判可以通过判断奇偶性来判断能否通过这个楼梯，如果不能通过且过楼梯后的那一个没有被搜索到，则在原地等一分钟再过楼梯。这里注意一下过从楼梯一边走到另一边只需要一分钟。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 30;
struct Node {
    int x, y;
    int step;
    Node() {}
    Node(int xx, int yy, int s) {
        x = xx;
        y = yy;
        step = s;
    }
};
bool operator==(const Node &a, const Node &b) {
    return a.x == b.x && a.y == b.y;
}
int n, m;
Node s, t;
queue<Node> que;
char G[maxn][maxn];
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool vis[maxn][maxn];
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
    int ret;
    while(!que.empty()) {
        que.pop();
    }
    memset(vis, 0, sizeof(vis));
    que.push(s);
    vis[s.x][s.y] = true;
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        if(tmp == t) {
            ret = tmp.step;
            break;
        }
        for(int i = 0; i < 4; ++i) {
            int xx = tmp.x + dir[i][0];
            int yy = tmp.y + dir[i][1];
            if(in(xx, yy)) {
                if(G[xx][yy] == 0 || G[xx][yy] == 1) {
                    int tmpx = xx + dir[i][0];
                    int tmpy = yy + dir[i][1];
                    if(in(tmpx, tmpy) && !vis[tmpx][tmpy]) {
                        if(((tmp.step & 1) ^ G[xx][yy] ^ (i & 1)) == 1) {
                            que.push(Node(tmp.x, tmp.y, tmp.step + 1));
                        } else {
                            vis[tmpx][tmpy] = true;
                            que.push(Node(tmpx, tmpy, tmp.step + 1));
                        }
                    }
                } else if(!vis[xx][yy] && G[xx][yy] != '*') {
                    vis[xx][yy] = true;
                    que.push(Node(xx, yy, tmp.step + 1));
                }
            }
        }
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%s", G[i]);
            for(int j = 0; j < m; ++j) {
                if(G[i][j] == 'S') {
                    s.x = i;
                    s.y = j;
                    s.step = 0;
                } else  if(G[i][j] == 'T') {
                    t.x = i;
                    t.y = j;
                } else if(G[i][j] == '|') {
                    G[i][j] = 0;
                } else if(G[i][j] == '-') {
                    G[i][j] = 1;
                }
            }
        }
        printf("%d\n", bfs());
    }
    return 0;
}

B. 变形课

题解

如果一个单词的首字母为 $x$ ，最后一个字母为 $y$ ，则在一个邻接矩阵上标记，表示可以从 $x$ 到达 $y$ ，然后从 $'b'$ 开始宽搜，看能否到达 $'m'$ ，可以则输出 $Yes.$ ，不能则输出 $No.$ ，注意输出时不要漏了句号。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 30;
string str;
queue<int> que;
bool vis[maxn];
bool G[maxn][maxn];
bool bfs() {
    while(!que.empty()) {
        que.pop();
    }
    memset(vis, 0, sizeof(vis));
    vis['b' - 'a'] = true;
    que.push('b' - 'a');
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        if(tmp == 'm' - 'a') {
            return true;
        }
        for(int i = 0; i < 26; ++i) {
            if(G[tmp][i] && !vis[i]) {
                vis[i] = true;
                que.push(i);
            }
        }
    }
    return false;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(cin >> str) {
        if(str[0] == '0') {
            printf("No.\n");
            continue;
        }
        memset(G, 0, sizeof(G));
        G[str[0] - 'a'][str[str.length() - 1] - 'a'] = true;
        while(cin >> str, str[0] != '0') {
            G[str[0] - 'a'][str[str.length() - 1] - 'a'] = true;
        }
        if(bfs()) {
            printf("Yes.\n");
        } else {
            printf("No.\n");
        }
    }
    return 0;
}

广度优先搜索

bfs

bfs 思路

bfs 代码实现

bfs 应用

2 月 13~14 日 bfs 练习题解

A. Knight Moves

题意

数据范围

题解

过题代码

B. Catch That Cow

题意

数据范围

题解

过题代码

C. Dating with girls(2)

题意

数据范围

题解

过题代码

2月15日 bfs 练习题解

A. Nightmare

题意

数据范围

题解

过题代码

B. 诡异的楼梯

题解

过题代码

B. 变形课

题解

过题代码

内容目录