#创作计划# BFS深度优先搜索
2026-07-27 17:15:36
发布于：浙江
12阅读
0回复
0点赞
前言：
- 本帖是讲解的，阅读前需要会编写A+B problem（被删了，所以你得有会编写A+B）的编程石粒，以语文分数不低于0分的石粒
- 为了维持ACGO的风度，所以大部分代码为伪代码，防止有神秘人直接复制粘贴。
- 代码有很多我打比赛保留的一些习惯，可跳过，因为本来就没用
- 废话不多说直接
结束开始
正片
-
1.了解：
- ，英译：广度优先搜索
- 同事：等
- 核心用处：用于走迷宫（多用于求最短路），遍历图/树等
- 中心思想：“泼水，向四周蔓延”，沿着一个点向外不停延伸，直到不能延伸。
- 拿走迷宫举例（本图选自A8036的样例1）（有点糊，请见谅）
- 看一看这个图，可以发现究竟为何适合求最短路，因为它是由一个点不停向外延伸，所以第一次找到终点那一定就是最短的路
- 拿走迷宫举例（本图选自A8036的样例1）（有点糊，请见谅）
-
2.尝试实现
- 因为是从一个点向外延伸，那么我们需要用一个容器来进行存储遍历，这里推荐用——队列（先进先出），进行存储
- 因为大部分用于迷宫，所以这里编写的就仅仅适用于迷宫（因为我真的想不到还可以干啥了）
- 可以封装成函数，但我喜欢不封装，这里就展示不封装的了
struct node { 创建变量用于存储位置信息以及需要步数 }; …… queue<node> q; q.push({起始x, 起始y, 从起始位置(x, y)走到(x, y)需要0步}); 将此点设为已访问 while (!q.empty()) { 模拟向外延伸直到无路可走 int 创建变量获取当前x和y以及需要的步数; 弹出这个结点，防止死循环 if (到达终点) { 输出需要的步数 return 0; } for (尝试向4个方向进行蔓延) { int 创建变量存储新的x; int 创建新的变量存储新的y; if (越界) continue; if (已访问) continue; if (是障碍物) continue; 将此点设为已访问 q.push({新的x, 新的y, 步数 + 1}); } } 输出无法到达 -
因为我
是甜菜真的想不到还可以干啥了，随意没有完善代码环节，直接上实战吧！ -
3.实战：
-
T1：A8036.走迷宫（没错还是他）
-
(1). 分析题目：
- 很朴素的，告诉你地图，让你求从(1, 1) 到 (R, C) 的最短路
-
(2). 代码思路：
- 直接用模版即可，注意"计算步数要包括起点和终点"这句话
-
(3). 代码实现:
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 50; int n, m; //我喜欢 你别管 char mp[N][N]; bool vis[N][N]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; struct node { int x, y, cnt; }; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); // freopen("", "r", stdin); // freopen("", "r", stdout); 输入 n, m, mp; queue<node> q; q.push({起始x —— 1, 起始y —— 1, 所需步数（包裹起点）—— 1}); vis[1][1] = true; while (!q.empty()) { int x = 当前x; int y = 当前y; int cnt = 到(x, y)需要的步数 q.pop(); if (x == n && y == m) { 到达输出cnt return 0; } for (枚举4个方向) { int nx = 新的x; int ny = 新的y; if (越界) continue; if (已访问) continue; if (是障碍物) continue; vis[nx][ny] = true; q.push({nx, ny, cnt + 1}); } } 因为题目保证一定能走到，所以这了不用写任何东西，写了也不会执行 return 0; } -
-
T2：A8037.腐烂的橘子
-
(1). 分析题目：
- 这道题虽然不是走迷宫（终于让我找到了），但是它的题目就是，因为这道题的中心思想是从个点（n = 新腐烂的橘子数）向四周蔓延，感染其他橘子
-
(2). 代码思路：
- 利用每一次取出它里面原有的所有位置向四周扩散感染
-
(3). 代码实现:
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1010; int n, m; int mp[N][N]; bool vis[N][N]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; struct node { int x, y; }; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); // freopen("", "r", stdin); // freopen("", "r", stdout); queue<node> q; int time = 0, cnt = 0; time记录需要多少时间 cnt表示还剩几没有腐烂的橘子 cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> mp[i][j]; vis[i][j] = false; if (mp[i][j] == 2) { 加入q，并标记为已访问，防止多次访问 } if (mp[i][j] == 1) { 没有腐烂cnt+1 } } } while (!q.empty()) { if (没有没有腐烂的橘子了) { 输出时间 return 0; } time++; for (int l = q.size(); l >= 1; l--) { 取出q中原有的所有位置 int x = 现在的x； int y = 现在的y; 弹出，防止死循环 for (枚举4个方向) { int nx = 新的x; int ny = 新的y; if (越界) continue; if (已访问) continue; if (是空的) continue; 这里不需要判断是不是腐烂的橘子是因为腐烂的橘子肯定已经访问过了 标记为已访问 q.push({加入}); 没有腐烂的橘子数减少1 } } } // 其实这里应该还得判断cnt等不等于0,但数据太水了,不判断也能AC 不可能输出-1 return 0; } -
-
T3：A272.青蛙跳杯子
-
(1). 分析题目：
- 不要被这道题的难度唬住了，其实特别简单，说白了就是枚举所有可能，所以可能也能做(吗？）
-
(2). 代码思路：
- 枚举出所有目前字符串可以演变的所有可能，我一开始没看清楚，了9次😐
-
(3). 代码实现:
- 这题我写了题解，你可以瞅瞅
#include<bits/stdc++.h> #define int long long using namespace std; string a, b; struct node { string s; int cnt; }; queue <node> q; map<string, bool> vis; // 记录此状态是否出现过 signed main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); // freopen("", "r", stdin); // freopen("", "r", stdout); cin >> a >> b; //输入a，b q.push({a, 0}); // 将a加入q中 vis[a] = true; // 将此状态改为已访问= while (!q.empty()) { string s = q.front().s; // 取出当前字符串 int cnt = q.front().cnt; // 取出当前所需步数 q.pop(); // 弹出避免死循环 if (s == b) { // 已经达成b cout << cnt; // 输出 return 0; } for (遍历整个字符串) { if (找到空杯子) { for (尝试6个方位) { int k = 新的位置; if (不越界) { 交换i和k if (未出现此状态) { 更新状态为已出现 q.push({新的字符串, cnt + 1}); } } 恢复，但如果你是用新的字符串进行调换的话就不需要恢复 } 跳出循环防止超时 } } } return 0; }
-
-
3.结尾：
- 目前因时间关系，仅写了一些题目，后面会陆续写一些，同时欢迎投稿题目，如果我写的来我就写，并且会标注投稿人的名字；你也可以补充、纠正，我看到了会改，没看的话你就疯狂**@我**把
有帮助，赞一个