首页 > 编程语言 >【普及组】广度优先搜索BFS——到达型搜索问题_C++算法竞赛

【普及组】广度优先搜索BFS——到达型搜索问题_C++算法竞赛

时间：2024-07-21 23:29:46浏览次数：16  
标签：tx ty int cin C++ BFS vis 搜索 &&

文章目录

提示：本文建议有一定基础的学员阅读，如果初学建议根据本文的引导做题，做完之后多到题解区里看看，巩固知识。

1. 走迷宫

在二维矩阵中，有空地和障碍若干，根据题目要求可以走到周围的四个格子（上 下 左 右）或八个格子（上 下 左 右 左上 左下 右上 右下），求能否从一个位置到达另一个位置。

同时，一些格子还可以触发回血等特殊功效。在写代码时特判一下即可。

走迷宫问题的要点：

  1. 广搜用队列存储所有要搜索的点，因为队列的先进先出性质，所以队头的元素一定是当前走的步数最少的。
  2. 广搜的重要性质：在所有路径长度一致、其他影响量都一致时，第一次到达某个格子时的步数一定为当前最优解。即每个格子只需要到达一次就有最优解。这也是 bfs 只需要标记一次，而 dfs 需要回溯 的原因。

注：若有除步数之外的其他影响量，可以用 v i s vis vis 数组标记上次到达某个格子的最优影响量。如果再次到达这个格子时，影响量更优，那么就更新 v i s vis vis 数组。这样可以找到最优解。

  1. 可以用标记数组 v i s vis vis 标记某个格子是否曾经到过，也可以直接在原图中把当前格子标记为障碍，这样都可以达到之后不再走这个格子的效果。
  2. 用两个偏移量数组 d x , d y dx,dy dx,dy 来控制四个 / 八个行走的方向。

例1.洛谷B3625 迷宫寻路

Link：Luogu - B3625

走迷宫的模板题。注意代码里的注释，有一些写代码的细节

#include <bits/stdc++.h>
using namespace std;

int n , m;
char a[105][105];
const int dx[] = {0, 1, 0, -1}; // x的偏移量数组，用来控制x坐标下一步往哪走
const int dy[] = {1, 0, -1, 0}; // y的偏移量数组

struct Node{
	int x, y; // 表示当前的x，y坐标
};

bool bfs()
{
	queue <Node> q; 
	q.push({0 , 0});
	while(!q.empty()){
		Node it = q.front(); q.pop();
		if(it.x == n - 1 && it.y == m - 1){ // 说明到达终点
			return true;
		}
		for(int i = 0; i < 4; i ++){
			int tx = it.x + dx[i];
			int ty = it.y + dy[i];
			if(tx >= 0 && tx < n && ty >= 0 && ty < m && a[tx][ty] != '#'){ // 判断下一步是否在网格图内（不越界）且不是障碍
				a[tx][ty] = '#'; // 一个位置只要走一次就可以。这里可以直接把它标记为障碍，这样以后就不会走过来了
				q.push({tx , ty}); // 加入队列继续搜索
			}
		}
	}
	return false;
}

signed main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	if(bfs() == true){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

如果上面的题目更改为八方向，只需对 d x , d y dx,dy dx,dy 数组微调一下即可：

#include <bits/stdc++.h>
using namespace std;

int n , m;
char a[105][105];
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}; // x的偏移量数组，用来控制x坐标下一步往哪走
const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1}; // y的偏移量数组

struct Node{
	int x, y; // 表示当前的x，y坐标
};

bool bfs()
{
	queue <Node> q; 
	q.push({0 , 0});
	while(!q.empty()){
		Node it = q.front(); q.pop();
		if(it.x == n - 1 && it.y == m - 1){ // 说明到达终点
			return true;
		}
		for(int i = 0; i < 8; i ++){
			int tx = it.x + dx[i];
			int ty = it.y + dy[i];
			if(tx >= 0 && tx < n && ty >= 0 && ty < m && a[tx][ty] != '#'){ // 判断下一步是否在网格图内（不越界）且不是障碍
				a[tx][ty] = '#'; // 一个位置只要走一次就可以。这里可以直接把它标记为障碍，这样以后就不会走过来了
				q.push({tx , ty}); // 加入队列继续搜索
			}
		}
	}
	return false;
}

signed main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	if(bfs() == true){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

例2.洛谷P1825 [USACO11OPEN] Corn Maze S

Link：Luogu - P1825

这道题就是多加上了一个传送门，由于题面给的比较简单，只要一到了传送门处，就一定要移动，那么只要特判一下：只要到了传送门，就移动到对应位置即可。

#include <algorithm>
#include <cctype>
#include <queue>
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;

char a[305][305];
int n,m;
int dis[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };

struct Pos
{
	int x,y,step;	//结构体：xy坐标，步数
	Pos(int a = -1, int b = -1, int c = 0) :
		x(a), y(b), step(c) {}
};
queue<Pos> que; //广搜队列
Pos trans[150][3]; //记录传送门

bool vis[305][305];
int sx,sy,ex,ey;

void goto_pos(int &x, int &y)
{
	char ch = a[x][y];
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			if (a[i][j]==ch && (i!=x || j!=y))
			{
				x = i;
				y = j;
				return ;
			}
		}
	}
}

int bfs()
{
	que.push(Pos{sx,sy,0});
	a[sx][sy] = '#';
	
	while (!que.empty())
	{
		Pos it = que.front();	que.pop();
		
		if (it.x==ex && it.y==ey)
		{
			return it.step;
		}
		
		if (isupper(a[it.x][it.y]))
		{
			goto_pos(it.x, it.y);
		}
		
		for (int i=0; i<4; i++)
		{
			int tx = it.x + dis[i][0];
			int ty = it.y + dis[i][1];
			
			if (tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]!='#')
			{
				if (!isupper(a[tx][ty]))	a[tx][ty] = '#';
				que.push(Pos{tx,ty,it.step+1});
			}
		}
	}
	
	return -1;
}

signed main()
{
	scanf("%d %d", &n, &m);
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == '@') sx=i, sy=j;
			if (a[i][j] == '=') ex=i, ey=j;
		}
	}
	printf("%d\n", bfs());
	return 0;
}

例3.[ABC348D] Medicines on Grid（AtCoder）

Link：Luogu - AT_abc348_d

这道题的花样在于：网格上的药可以吃，也可以不吃，但吃完一次之后就没了。

因为 bfs 有天生的首次到达必定是最优解的特性，所以可以标记 vis 数组。
vis[x][y] 表示到达 (x,y) 位置时的最优血量，只有当前血量比上次更优时才继续搜索。
还要用一个小贪心：如果吃了药能变得更强，就一定要吃药。这样肯定更优（或不劣）

自己写代码时的技巧：
a[x][y]=0：空地.
a[x][y]=400：障碍#
a[x][y]=500：起点S
a[x][y]=600：终点T
a[x][y]>=1 and a[x][y]<=300：表示(x,y)位置是第a[x][y]个药
这样写最方便的就是走到(x,y)，就知道有没有药，还可以直接根据下标获取药物的贡献，实现比较简便

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int h, w, a[205][205], E[305];
int sx, sy, ex, ey;
struct Node{
	int x, y, e;
};
const int d[][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};
int vis[205][205];

void solve()
{
	cin >> h >> w;
	for(int i = 1; i <= h; i ++){
		for(int j = 1; j <= w; j ++){
			char c; cin >> c;
			if(c == '#') a[i][j] = 400;
			else if(c == 'S') a[i][j] = 500, sx = i, sy = j;
			else if(c == 'T') a[i][j] = 600, ex = i, ey = j;
			vis[i][j] = -1e9;
		}
	}
	int n; cin >> n;
	for(int i = 1, r, c; i <= n; i ++){
		cin >> r >> c >> E[i];
		a[r][c] = i;
	}
	
	queue <Node> Q;
	Q.push({sx, sy, 0});
	while(!Q.empty()){
		Node it = Q.front(); Q.pop();
		int x = it.x, y = it.y, e = it.e;
		if(x == ex && y == ey){
			cout << "Yes\n";
			return ;
		}
		if(a[x][y] > 0 && a[x][y] < 400){
			if(E[a[x][y]] > e){ // 如果吃药可以变得更强，就吃药
				e = E[a[x][y]];
				a[x][y] = 0; // 吃完药就变成空地
			}
		}
		for(int i = 0; i < 4; i ++){
			int tx = x + d[0][i], ty = y + d[1][i];
			if(tx >= 1 && tx <= h && ty >= 1 && ty <= w){
				if(e > vis[tx][ty] && e - 1 >= 0 && a[tx][ty] != 400){ // 如果当前血量比上一次到达的血量要高
					vis[tx][ty] = e;
					Q.push({tx, ty, e - 1});
				}
			}
		}
	}
	cout << "No\n";
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

2.生活背景下的常见问题

这种问题有三种解法：dfs、bfs、dp。这里讲解 bfs 做法。

其核心还是万变不离其宗，设置结构体数组表示当前的状态（走迷宫问题的状态就是位置、血量等），然后配合标记数组进行广搜即可。

例.P3958 [NOIP2017 提高组] 奶酪

Link：Luogu - P3958

讲一下 bfs 的思路：暴力且简单。

首先，把和下底面相交的所有元素全部加入队列中（可以用类似图论建边的方式），然后不断向上搜索，如果有 z + r ≥ h z+r \ge h z+r≥h，就说明到达了上底面，退出。

注意，每个点最多只能到一遍，用 v i s vis vis 数组标记一下即可。（因为这毕竟是暴力吗，跑得慢一点很正常）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

struct Node{
	int x, y, z; // 存储坐标
}p[maxn];

int n, h, r;

inline double sq(double x){ return x * x; } // 返回一个数平方
inline double dis(int i, int j){ // 求两点之间的距离
	return sqrt(sq(p[i].x - p[j].x) + sq(p[i].y - p[j].y) + sq(p[i].z - p[j].z));
}

void solve()
{
	cin >> n >> h >> r;
	for(int i = 1; i <= n; i ++){
		cin >> p[i].x >> p[i].y >> p[i].z;
	}
	
	vector <int> t[n + 1]; // 预处理所有相切的孔。t[i]表示所有与第i个洞相切的洞的序号
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){ // 从i+1开始升序枚举，避免重复
			if(dis(i, j) <= 2*r){ // 如果两圆心距离<=2r，则它们可以互相到达
				t[i].push_back(j);
				t[j].push_back(i); // 互相加入列表中
			}
		}
	}
	
	queue <int> Q; // 存储点的下标
	vector <int> vis(n + 1, 0); // vis[i]表示第i个球是否访问过
	bool flag = false; // 是否能到达上表面
	for(int i = 1; i <= n && !flag; i ++){
		if(p[i].z - r <= 0){ // 如果与下表面相切，则可以直接进入
			Q.push(i);
			vis[i] = 1;
			if(r + p[i].z >= h) flag = true; // 如果直接能到达上底面，就直接标记
		}
	}
	
	while(!flag && Q.size()){
		int u = Q.front(); Q.pop();
		for(int v : t[u]){ // 遍历所有与u相邻的球
			if(flag) break; // 如果有答案了就不用再遍历了
			if(!vis[v]){
				Q.push(v);
				vis[v] = 1;
				if(r + p[v].z >= h) flag = true; // 如果直接能到达上底面，就直接标记
			}
		}
	}
	
	cout << (flag? "Yes\n" : "No\n");
}

signed main()
{
	int T; cin >> T;
	while(T --) solve();
	return 0;
}

3.输出路径

输出路径的核心方法：用类似单向链表（链式前向星）的形式，对于每个状态，存储它的前一个所在位置。输出时可以用递归的方法，这样就把原来的倒序输出变成了顺序输出。

具体看代码实现。

例.洛谷P6207 [USACO06OCT] Cows on Skates G

Link：Luogu - P6207

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node{
	int x, y, p, id; // p是指向前一个路径的指针，id是当前位置的下标
}n[100005]; // 移动次数<=1e5

int r, c;
char a[115][80];
int vis[115][80]; // 标记数组
int d[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 偏移量数组

void print(int u){ // 打印路径
	if(u == -1) return ;
	print(n[u].p);
	cout << n[u].x << ' ' << n[u].y << '\n';
}

void solve()
{
	cin >> r >> c;
	for(int i = 1; i <= r; i ++){
		for(int j = 1; j <= c; j ++){
			cin >> a[i][j];
		}
	}
	
	queue <Node> Q;
	int cnt = 1; // n数组的指针
	n[1] = {1, 1, -1, 1}; // 第一个的前一个位置设为-1，便于输出时判断
	Q.push(n[1]); 
	vis[1][1] = 1;
	while(Q.size()){
		Node it = Q.front(); Q.pop();
		
		if(it.x == r && it.y == c){
			print(it.id);
			return ;
		}
		
		for(int i = 0; i < 4; i ++){
			int tx = it.x + d[i][0], ty = it.y + d[i][1];
			if(tx >= 1 && tx <= r && ty >= 1 && ty <= c && !vis[tx][ty] && a[tx][ty] != '*'){
				++ cnt;
				n[cnt] = {tx, ty, it.id, cnt}; // 前一个位置是it.id
				vis[tx][ty] = 1;
				Q.push(n[cnt]);
			}
		}
	}
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

End

本文的讲解就到这里了，希望大家喜欢！

这里是 YLCHUP，拜拜ヾ(•ω•`)o

标签：tx,ty,int,cin,C++,BFS,vis,搜索,&&
From： https://blog.csdn.net/YLCHUP/article/details/140585738

相关文章

  • 【机器学习】FastGPT 知识库搜索测试功能解析
    本文以FastGPT知识库的搜索测试功能为入口，分析FastGPT的知识检索流程。一、搜索功能介绍1.1整体介绍搜索测试功能包含三种类型：语义检索、全文检索、混合检索。语义检索：使用向量进行文本相关性查询，即调用向量数据库根据向量的相似性检索；全文检索：使用传统的全文检索，适......
  • C++引用（reference）
    在C++中，引用（reference）是一个已存在变量的别名，它允许你为变量提供一个或多个额外的名字。引用在定义时必须初始化，并且一旦初始化后，就不能再引用其他变量。引用和它所引用的变量共享相同的内存地址。以下是C++中引用的基本用法：cpp#include<iostream>intmain(){inta=10;......
  • c++ class 和继承
    c++class和继承  #include<iostream>#include<string> //基类classAnimal{protected:std::stringname;public:Animal(conststd::string&name_param):name(name_param){}virtualvoidspeak()const=0;//纯虚函数，派生类需要实现}......
  • C++标准模板（STL）- 概念库 (C++20) - 指定一个类型派生自另一类型 - （std::derived_from）
    概念库提供基础语言概念的定义，它们能用于进行模板实参的编译时校验，以及基于类型属性的函数派发。这些概念在程序中提供等式推理的基础。标准库中的大多数概念一同加上了语法及语义要求。通常，编译器只能检查语法要求。若在使用点语义要求未得到满足，则程序为病式，不要求诊断。......
  • C++11(2): 通用
    31.继承构造函数structB:A{usingA::A;};32.委派构造函数classA{public: A() :A(1234){}//先调用A(int) A(intn1):A(n1,'C'){}//先调用A(int,char) A(charc1):A(2,c1){}//先调用A(int,char)private: A(intn2,charc2):my_......
  • c++ 引用和指针
      c++引用和指针在C++中，引用和指针是两个非常重要的概念，它们有一些相似之处也有一些不同之处。相似之处：引用和指针都可以指向一个对象。引用一旦被初始化指向一个对象后，就不能再指向其他对象，而指针可以在任何时候指向其他对象。不同之处：引用在......
  • 快速完成VsCode C/C++开发环境配置
    前言本人在配置VsCodeC++开发环境时，查看了很多的博客，内容参差不齐，尤其是关于json文件的配置，绕的人头很晕，最终还是通过阅读官方文档，结合部分博客的指引，完成了环境的配置，在此记录本人的配置过程，希望能帮助到大家。事先声明，本文的内容大量引自VsCode官方的文章：https://code.visual......
  • 神经架构搜索：目标检测的未来
    神经架构搜索：目标检测的未来在深度学习领域，神经架构搜索（NeuralArchitectureSearch,NAS）是一种自动化设计神经网络结构的技术。它通过机器学习的方法来探索最优的网络结构，从而提高模型的性能。在目标检测任务中，NAS的应用尤为显著，因为它可以帮助研究人员和开发者快速找到适......
  • OpenCV 遍历Mat，像素操作，使用TrackBar 调整图像的亮度和对比度 C++实现
    文章目录1.使用C++遍历Mat,完成颜色反转1.1常规遍历方式1.2迭代器遍历方式1.3指针访问方式遍历（最快）1.4不同遍历方式的时间对比2.图像像素操作，提高图像的亮度3.TrackBar进度条操作3.1使用TrackBar调整图像的亮度3.2使用TrackBar调整图像的对比度1.使用C++遍历M......
  • C++吃豆人~
    #include<cstdio>#include<iostream>#include<ctime>#include<conio.h>#include<windows.h>#include<cstdlib>#include<cstring>usingnamespacestd;constintn=809;structPoint{intx,y;};intdali;intfx[......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99