广度优先搜索
1.什么是广度优先搜索?
广度优先搜索（Breadth-First Search，简称BFS）是一种遍历或搜索树和图的算法，也称为宽度优先搜索，BFS算法从图的某个节点开始，依次对其所有相邻节点进行探索和遍历，然后再对这些相邻节点的相邻节点进行探索，直到遍历完所有的节点。
2.c++与c语言的实现的不同
c++ BFS算法使用队列来辅助实现,c语言往往通过数组来辅助实现(后面会有不同的样例来解释不同的语言的实现形式)c语言看起来可能有点啊难理解，需要通过模拟队列!
3.BFS的使用场景
一般来说广度优先搜索适用于解决两点之间的最短路径问题
广度优先搜索是从起点出发，以起点为中心，一圈一圈搜索的，一旦找到终点，记录之前走过的节点，这样就是一条最短路径
BFS常用于寻找最短路径,数据小的最短路径可以用DFS,大点的用DFS会超时,之前写过一道,这样子的题型
DFS/BFS算法在蓝桥杯竞赛中很常见。几乎每一年都会考到DFS/BFS算法!
4.BFS的使用步骤
将起始节点放入队列中,然后将起点标记为已经访问过，然后依次取出队列中的节点，访问其相邻节点，并将其加入队列。这样可以保证从起始节点出发，依次按照距离顺序遍历节点。因为它按照从起点到每个节点的距离来探索节点。
BFS算法通常使用队列来实现，BFS算法的具体步骤如下：
创建一个队列，将起始节点加入队列；
创建一个集合，用于存储已经访问过的节点；
从队列中取出一个节点，并将其标记为已访问；
访问该节点的所有相邻节点，如果相邻节点未被访问，则将其加入队列；
重复步骤3和步骤4，直到队列为空。
5.算法模板：
首先我们需要一个队列来辅助BFS实现，还需要一个初始化的输入数组，还有一个标记数组。先找到BFS的起点跟终点，确定好之后，先把起点vis==1，把起点入队，然后进入BFS函数，进入BFS函数一般先是一个大while循环，来管理队列的入队、出队。由于点都是二维的，我们一般都是用pair或者结构体来表示点，新建一个点来存储队头的信息，存完就可以让队头出队了。然后判断是否到达了目标结点，一个if判断，下面就是跟dfs一样，一个for循环遍历周围所有的点，不合法的直接continue掉，合法的标记完vis后入队，有的题目会有回溯，像在部分最短路搜索。
queue<node> q;
void bfs(){while(!q.empty()){node tmp=q.top();//node为(x,y)结构体q.pop();//出队if(到达目标终点){更新return;}//有的会有剪枝for(int i=0;i<m;i++){//m个方向int dx=tmp.x+bx[i];int dy=tmp.y+by[i];if(下标越界){continue;}if(已经被标记过了){continue;}//否则就是合法的vis[dx][dy]=1;//先标记q.push(node{dx,dy});//再新点入队}}
}P1443 马的遍历 - 洛谷
如有不懂,可以发在评论区,谢谢,有时间我就会回答的!!!
#include<bits/stdc++.h>
using namespace std;// 定义棋盘的行数和列数，以及马的起始位置
int n, m, x, y;// 定义马的8个移动方向（日字形移动）
int ax[] = {1, 1, 2, 2, -1, -1, -2, -2}; // 横坐标变化
int ay[] = {2, -2, 1, -1, 2, -2, 1, -1}; // 纵坐标变化// 定义步数数组，用于存储每个点的最短步数
int Map[1000][1000];// 定义结构体，表示棋盘上的一个点
struct pos {int x, y; // 点的横纵坐标
};// BFS函数，用于计算马从起点到棋盘上任意一点的最短步数
void bfs() {queue<pos> qu; // 定义队列，用于BFS遍历pos cur; // 当前点qu.push({x, y}); // 将起点入队// BFS主循环，直到队列为空while (!qu.empty()) {cur = qu.front(); // 取出队首元素qu.pop(); // 将队首元素出队// 遍历马的8个移动方向for (int i = 0; i < 8; i++) {int nx = cur.x + ax[i]; // 计算新位置的横坐标int ny = cur.y + ay[i]; // 计算新位置的纵坐标// 检查新位置是否超出棋盘边界if (nx > n || ny > m || nx < 1 || ny < 1) continue;// 如果新位置未被访问过（步数为-1）if (Map[nx][ny] == -1) {Map[nx][ny] = Map[cur.x][cur.y] + 1; // 更新步数qu.push({nx, ny}); // 将新位置入队}}}
}int main() {// 初始化步数数组为-1，表示所有点未被访问memset(Map, -1, sizeof(Map));// 输入棋盘的行数、列数以及马的起始位置cin >> n >> m >> x >> y;// 设置起点的步数为0Map[x][y] = 0;// 调用BFS函数，计算从起点到棋盘上任意一点的最短步数bfs();// 输出结果for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {printf("%d ", Map[i][j]); // 输出每个点的最短步数}printf("\n"); // 每行末尾换行}return 0;
}问题 - 2612 --- Problem - 2612
方法一(蒟蒻刚写并且经历千辛万苦就是这样的)
#include<bits/stdc++.h>
using namespace std;// 全局变量声明
int n, m; // 迷宫的行数n和列数m
int si, sj, di, dj; // Y的起点坐标(si,sj)和M的起点坐标(di,dj)
int b[202], c[202]; // 存储所有@点(汇合点)的坐标
int vis[202][202]; // Y的BFS访问标记数组
int vis2[202][202]; // M的BFS访问标记数组
char a[202][202]; // 存储迷宫地图
int Map[202][202]; // 记录Y到各点的最短距离
int Map2[202][202]; // 记录M到各点的最短距离struct pos { // 坐标结构体，用于队列存储int x, y;
};// 方向数组：上下左右四个方向
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};void bfs() {queue<pos> q, w; // 两个队列分别处理Y和M的BFS// Y的BFS初始化q.push({si, sj});vis[si][sj] = 1; // 标记起点已访问Map[si][sj] = 0; // 起点到自身距离为0// 处理Y的BFSwhile (!q.empty()) {pos cur = q.front();q.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {int u = cur.x + dx[i];int v = cur.y + dy[i];// 边界检查if (u < 0 || u >= n || v < 0 || v >= m) continue;// 可通行且未被访问if (!vis[u][v] && a[u][v] != '#') {vis[u][v] = 1;Map[u][v] = Map[cur.x][cur.y] + 1; // 距离递增q.push({u, v});}}}// M的BFS初始化w.push({di, dj});vis2[di][dj] = 1; // 标记起点已访问Map2[di][dj] = 0; // 起点到自身距离为0// 处理M的BFSwhile (!w.empty()) {pos net = w.front();w.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {int u = net.x + dx[i];int v = net.y + dy[i];// 边界检查if (u < 0 || u >= n || v < 0 || v >= m) continue;// 可通行且未被访问if (!vis2[u][v] && a[u][v] != '#') {vis2[u][v] = 1;Map2[u][v] = Map2[net.x][net.y] + 1; // 距离递增w.push({u, v});}}}
}int main() {while (cin >> n >> m) { // 循环处理多个测试用例// 初始化数组memset(Map, -1, sizeof(Map)); // 初始距离设为-1(不可达)memset(Map2, -1, sizeof(Map2));memset(vis, 0, sizeof(vis)); // 重置访问标记memset(vis2, 0, sizeof(vis2));int k = 0; // @点计数器// 读取迷宫数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i][j];if (a[i][j] == '#') { // 障碍物处理vis[i][j] = vis2[i][j] = 1; // 标记为已访问（不可通过）} else if (a[i][j] == 'Y') { // Y的起点si = i; sj = j;vis[i][j] = 1; // 标记已访问Map[i][j] = 0; // 初始距离为0} else if (a[i][j] == 'M') { // M的起点di = i; dj = j;vis2[i][j] = 1; // 标记已访问Map2[i][j] = 0; // 初始距离为0} else if (a[i][j] == '@') { // 存储汇合点坐标b[k] = i;c[k++] = j;}}}bfs(); // 执行双向BFS// 计算最小总距离int min_sum = INT_MAX;for (int i = 0; i < k; i++) {if (Map[b[i]][c[i]]!=-1 && Map2[b[i]][c[i]]!=-1)min_sum = min(min_sum, Map[b[i]][c[i]] + Map2[b[i]][c[i]]);}cout << min_sum * 11 << endl; // 输出结果（每步耗时11分钟）}return 0;
}这是AI写的太强大了,以后我只能去干java炒饭了,大佬们
#include <iostream>
#include <queue>
#include <climits>
using namespace std;struct pos { int x, y; };
int dx[] = {1,-1,0,0}, dy[] = {0,0,-1,1};
int n, m, si, sj, di, dj;
char grid[202][202];
int distY[202][202], distM[202][202];void bfs(int sx, int sy, int dist[][202]) {queue<pos> q;q.push({sx, sy});dist[sx][sy] = 0;while (!q.empty()) {pos cur = q.front(); q.pop();for (int i = 0; i < 4; i++) {int nx = cur.x + dx[i], ny = cur.y + dy[i];if (nx >=0 && ny >=0 && nx <n && ny <m && grid[nx][ny] != '#' && dist[nx][ny] == -1) {dist[nx][ny] = dist[cur.x][cur.y] + 1;q.push({nx, ny});}}}
}int main() {while (cin >> n >> m) {vector<pair<int,int>> targets;memset(distY, -1, sizeof(distY));memset(distM, -1, sizeof(distM));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];if (grid[i][j] == 'Y') si = i, sj = j;if (grid[i][j] == 'M') di = i, dj = j;if (grid[i][j] == '@') targets.push_back({i,j});}}bfs(si, sj, distY);bfs(di, dj, distM);int min_steps = INT_MAX;for (auto &p : targets) {int y_dist = distY[p.first][p.second];int m_dist = distM[p.first][p.second];if (y_dist != -1 && m_dist != -1)min_steps = min(min_steps, y_dist + m_dist);}cout << (min_steps == INT_MAX ? 0 : min_steps * 11) << endl;}return 0;
}P1019 [NOIP 2000 提高组] 单词接龙 - 洛谷
方法一
#include<bits/stdc++.h>
using namespace std;int n, ans; // n: 单词数量, ans: 记录最长的龙单词长度
string str[30]; // 存储所有单词
int used[30]; // 记录每个单词的使用次数// 检查两个单词是否可以拼接，并返回可以重叠的字符数
int check(string a, string b) {int la = a.length();int lb = b.length();for (int i = 1; i <= min(la, lb); i++) { // 检查重叠部分if (a.substr(la - i) == b.substr(0, i)) { // 如果重叠部分匹配return i; // 返回重叠的字符数}}return 0; // 如果不能拼接，返回 0
}// 深度优先搜索，尝试拼接单词
void dfs(string s, int len) {ans = max(ans, len); // 更新最长的龙单词长度for (int i = 0; i < n; i++) { // 遍历所有单词int c = check(s, str[i]); // 检查当前单词是否可以拼接if (used[i] >= 2) continue; // 如果单词已经使用过两次，跳过if (c > 0) { // 如果可以拼接used[i]++; // 标记单词为已使用dfs(str[i], len + str[i].length() - c); // 递归拼接下一个单词used[i]--; // 回溯，取消标记}}
}int main() {cin >> n; // 输入单词数量for (int i = 0; i < n; i++) {cin >> str[i]; // 输入每个单词}string S;cin >> S; // 输入龙头字符ans = 0; // 初始化 ansmemset(used, 0, sizeof(used)); // 初始化 used 数组dfs(S, S.length()); // 开始深度优先搜索，初始龙单词为龙头字符cout << ans << endl; // 输出最长的龙单词长度return 0;
}方法2
#include<bits/stdc++.h>
using namespace std;
int n, ans,longest;
string str[42],s,res;
int vis[42];
char head;
int check(string a, string b) {for (int i = a.length() - 1; i >= 0; i-- ) {if (a.substr(i) == b.substr(0,a.length() - i)) {return a.length() - i;}}return 0;
}
void dfs(string s,int dep) {if (s.length() > longest) {longest = s.length();res = s;}if (dep >= 2 * n + 1)return;for (int i = 1; i <= n * 2; i++) {if (dep == 1&&str[i][0]==head&vis[i]==0) {vis[i] = 1;dfs(s+str[i],dep+1);vis[i] = 0;}else if (dep >= 2 && vis[i] == 0) {int pos = check(s, str[i]);if (pos != 0) {vis[i] = 1;dfs(s+str[i].substr(pos), dep + 1);vis[i] = 0;}}}
}
int main() {cin >> n;for (int i = 1; i <= n; i++){cin >> str[i];}for (int i = 1+n; i <= 2*n; i++){str[i] = str[i - n];}cin >> head;dfs(s,1);cout << longest << endl;return 0;
}
