广度优先搜索--之重生之我是蒟蒻,从入坟到入坑式讲解
广度优先搜索
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;
// 设置起点的步数为0
Map[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的BFS
while (!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的BFS
while (!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; // 初始化 ans
memset(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;
}