浅说广度优先搜索（上）

前言

假设你现在身处一个迷宫之中，而你对这个迷宫完全不了解，你只知道其中一定有一个点是通往出口的。现在你有个天赋技能——无限分身，你以及你的分身可以在原地分裂出多个相同的人。问：你要如何做才能保证你能最快找到出口？

介绍

在搜索中，最重要的就是求解最短路，我们前面学习的求解最短路的办法无论怎么剪枝就会有重复路径，因为我们的方法都是尝试去走这条路，如果不行再返回，既然是尝试，那么肯定有错误路径。我们有没有办法直接让我们走的每一步路都一定是当前的最短路呢？
答案是有的，我们可以按层来搜索，从起点开始，搜索出所有第一层能到达的点，那么从起点到这些点的最短路就知道了，再从这些第一层能到达的所有点依次出发，那么能到达的所有点就是第二层的点，依次类推，那么对于任意一个点，第一次访问到的该点就是起点到该点的最短路径。

第一种办法就是用数组实现，像上面一样，每一层的点以此放入一个数组中，这样就需要我们开二维数组，第一维表示层数，但是我们不知道最多有多少层，也无法判断最多的一层有多少个点，所以开数组我们都需要开到最大，空间不够。
当然，我们发现只有相邻两层之间有关系，那么可以开滚动数组省空间。但是实际上我们发现，先被拓展的点，那么也先拓展其他点，典型的先进先出，所以开一个队列就搞定了。

思路、

（1）把起点放入队列，此时队列里面只有起点一个元素。
（2）遍历起点的所有方向，找出所有合理的并且没有被标记过的点放入队列中。
（3）当队头元素所有方向遍历完成后，队头元素出队，继续遍历当前队头元素的所有方向并且依次入队。
（4）重复执行上述操作，直到队列为空或者找到终点为止。如果队列为空，说明从起点到终点没有路径，如果找到终点，则当前路径长度就是最短路径长度

同样的，这里我们还是用数组来模拟队列（没学过的看我之前的文章）

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

int head=1,tail=1;
int dr[4][2]={{0,1},{1,0},{-1,0},{0,-1}},used[1000][1000];

struct Q{
	int x,y;
	int step;
}q[1001000];

int mp[1000][1000];
int main() {
	int x,y,X,Y,n;
	cin>>n;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
	cin>>x>>y>>X>>Y;
	q[tail].x=x;
	q[tail].y=y;
	q[tail].step=0;
	tail++;
	used[x][y];
	while (head<tail){
		for (int k=0;k<4;k++){
			int tx=q[head].x+dr[k][0];
			int ty=q[head].y+dr[k][1];
			if (tx<1||tx>n||ty<1||ty>n)continue;
			if (mp[tx][ty]==0&&used[tx][ty]==0){
				if (tx==X&&ty==Y){
					cout<<q[head].step+1;
					return 0;
				}
				used[tx][ty]=1;
				q[tail].x=tx;
				q[tail].y=ty;
				q[tail].step=q[head].step+1;
				tail++;
			}
		}
		head++;
	}

	return 0;
}

深搜和广搜的对比

深搜和广搜各有优缺点，从效率上看，深搜的时间复杂度远大于广搜，那么我们为什么还要学习深搜呢？因为广搜是按层拓展，处于每一层的点到起点的距离被认为是相等的，所以每一层的路径长度都必须相等，否则就不可以用广搜，所以深搜的使
用范围比广搜大。
深搜的范围不仅仅不如，很多难题不会做的时候，都需要打暴力，但是很多暴力不知道循环的终点，每次循环的变化量都不一样，所以就需要用深搜来打暴力，称为爆搜，所以学好深搜，并且熟练剪枝是很有必要的。

既然，广度优先搜索的效率远高于深度优先搜索，那么我们为什么还要学习深搜呢？广搜能不能完全代替深搜呢？

我们以前学习的深搜的题包括以下几类：
一：非最短路(只能用DFS)
（1）起点到终点的所有路径
（2）起点到终点的所有方案
二：最短路
（1）每走一步花费的代价一样(DFS和BFS)
（2）每走一步花费的代价不一样(只能用DFS)

综上所述，因为BFS是按层搜索，所以找到的起点到终点的距离一定是最短路径，并且搜索过一次就不会再搜索第二次了。同样的，当权值不同的时候，层次就会发生错误，第一次求出来的未必就是最短路。

双端队列的广搜

在一个n*n的方格中，有两种颜色的格子，在相同颜色之间移动不需要消耗体力，但是在不同颜色之间移动需要消化1个单位的体力，问给定一个起点和一个终点，求起点到终点的最小体力消耗。n<=2000

这就是一道典型的权值为0和1的搜索题，如果用深搜，n<=2000,肯定超时。如果用普通广搜，搜到一个点就放入队尾，肯定是错误的，因为不满足队列中消耗的递增性。所以我们要用双端队列bfs。如果是相同颜色，无消耗，即和当前队首元素的优先级是一样的，所以我们完全可以把该点放入队首，这样不影响整个队列的有序性。如果是不同的颜色，消耗+1，和普通广搜一样，放入队尾，仍然可以保持原来的优先级。虽然这种思路很简单，但是在写法细节上和普通广搜还是有一些区别，一定要熟悉两种写法，以免混淆在一起。
有的时候会出现一种奇怪的题，虽然每条路径的长度不完全相同，但是也有规律性，比如路径长度只有0和k(常数),并且数据范围很大n<=1000,如果用深搜，时间过不了，如果用广搜，感觉按层拓展又不对。
实际上，当路径长度为0的时候就表示在当前这一层，我们可以很容易用循环来实现，但是实际上我们可以用双端队列来实现。

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

struct node{
	int x,y;
	int step=0;
}st,ed,q[1000000];
int tail=10000,head=10000;//双端队列一定要留够空间
int mp[520][520],used[520][520],n;
int dr[4][2]={{0,1},{1,0},{-1,0},{0,-1}};

void bfs(node tmp){
	q[tail]=tmp;
	tail++;//手动模拟双端队列
	while(head<tail){
		tmp=q[head];
		if (tmp.x==ed.x&&tmp.y==ed.y){
			cout<<tmp.step;
			return;
		}
		head++;
		for (int i=0;i<4;i++){
			node T;
			T.x=tmp.x+dr[i][0];
			T.y=tmp.y+dr[i][1];
			if (T.x<=n&&T.x>=1&&T.y<=n&&T.y>=1&&used[T.x][T.y]==0){
				used[T.x][T.y]=1;
				if (mp[tmp.x][tmp.y]==mp[T.x][T.y]){//如果相同
					T.step=tmp.step;//则步数不变
					head--;//放入头
					q[head]=T;
				}else {
					T.step=tmp.step+1;//否则加1
					q[tail]=T;//放入尾
					tail++;
				}
			}
			
		}
	}
}
int main(){
	cin>>n;
	cin>>st.x>>st.y>>ed.x>>ed.y;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
	bfs(st);
	return 0;
}

广搜求方案数

广搜是没有重复路径的，当搜到终点的时候就会直接结束，但是很明显最短路径没有搜索完。当终点在第k层时，从第k-1层的某个点到达第k层的终点，此时搜索结束，但是还有第k-1层的其他点也可以到达终点，这些点的情况也需要考虑。所以在搜索的时候不能搜到终点就结束，而是先打一个标记，当搜索完终点所在这一层的所有点后结束才能保证所有到终点的路径都搜索到了，即当出队的点的路径长度等于起点到终点的最短路径时就可以结束了。
但是为了保证答案的正确性，我们需要记录从起点出发到任意一个点的最短路径的方案数，同时在统计答案时，累加上上一个点的方案数，而不是+1

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,step;
}q[510000],st,ed;
int n,m,k,head=1,tail=1;
int mp[1019][1010],used[1010][1010],num[1010][1010],dis[1010][1010];
int dr[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void bfs(node Point){
    q[tail]=Point;
    tail++;
    used[Point.x][Point.y]=1;
    num[Point.x][Point.y]=1;
    dis[Point.x][Point.y]=0;
    int flag=0;
    while (head<tail){
        Point=q[head];
        head++;
        for (int i=0;i<4;i++){
            node point;
            point.x=Point.x+dr[i][0];
            point.y=Point.y+dr[i][1];
            if (point.x>n||point.x<1||point.y>m||point.y<1)continue;
            if (mp[point.x][point.y]==0){
                if (used[point.x][point.y]==0){
                    if (point.x==ed.x&&point.y==ed.y){
                        flag=1;
                    }
                    used[point.x][point.y]=1;
                    q[tail]=point;
                    dis[point.x][point.y]=dis[Point.x][Point.y]+1;
                    num[point.x][point.y]=num[Point.x][Point.y];
                    tail++;
                }else if (used[point.x][point.y]==1&&dis[point.x][point.y]==dis[Point.x][Point.y]+1){
                    num[point.x][point.y]+=num[Point.x][Point.y];
                }
            }
        }
        if (flag==1&&dis[Point.x][Point.y]==dis[ed.x][ed.y]){
            cout<<dis[ed.x][ed.y]<<endl;
            cout<<num[ed.x][ed.y];
            return;
        }
    }
    cout<<"No Solution!";
}
int main(){
    int t1,t2;
	cin>>n>>m>>k;
    for (int i=0;i<k;i++){
        cin>>t1>>t2;
        mp[t1][t2]=1;
    }
	cin>>st.x>>st.y>>ed.x>>ed.y;
    if (st.x==ed.x&&st.y==ed.y){
        cout<<0;
        return 0;
    }
    bfs(st);
	return 0;
}

广搜求具体方案

广搜求具体方案和深搜求具体方案的方法类似，A点能够到达B点，那么B点的前驱就是A点，因为广搜每次走的都是最短路径，所以前驱一旦记录就不会发生改变。对于每一个点，单独开一个二维数组记录其前驱结点的行、列坐标，最后再从终点出
发一直找前驱直到找到起点为止。

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

struct node{
	int x,y,step;
}st,ed,q[520000],qian[1000][1000];
int tail=1,head=1,cnt;
int n,m;
int mp[1000][1000],used[1000][1000],dr[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int l[300000],r[300000];
void bfs(node t){
	q[tail]=t;
	tail++;
	while(head<tail){
		t=q[head];
		head++;
		for (int i=0;i<4;i++){
			node point;
			point.x=t.x+dr[i][0];
			point.y=t.y+dr[i][1];
			if (point.x==ed.x&&point.y==ed.y){
				qian[ed.x][ed.y]=t;
				cnt=t.step+1;
				return;
			}
			if (point.x>n||point.x<1||point.y>m||point.y<1){
				continue;
			}
			if (used[point.x][point.y]==0&&mp[point.x][point.y]==0){
				qian[point.x][point.y]=t;
				used[point.x][point.y]=1;
				point.step=t.step+1;
				q[tail]=point;
				tail++;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	cin>>st.x>>st.y>>ed.x>>ed.y;
	bfs(st);
	if (cnt==0){
		cout<<"No Solution!";
		return 0;
	}
	int lx=ed.x,ly=ed.y;
	l[0]=ed.x,r[0]=ed.y;
	cout<<cnt<<endl;
	for (int i=1;i<=cnt;i++){
		l[i]=qian[lx][ly].x,r[i]=qian[lx][ly].y;
		lx=l[i],ly=r[i];
	}
	for (int i=cnt;i>=0;i--){
		cout<<l[i]<<" "<<r[i]<<endl;
	}
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/608467.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

利用智能私信软件，快速拓展潜在客户群体

利用智能私信软件，快速拓展潜在客户群体

在数字化营销的浪潮中&#xff0c;企业如何快速而有效地触及并吸引潜在客户&#xff0c;已成为一个不可忽视的挑战。随着人工智能技术的不断进步&#xff0c;智能私信软件作为一种新型工具&#xff0c;正逐渐改变着企业的市场拓展方式。本文将探讨如何通过这类软件&#xff0c;…
阅读更多...
复现NerfingMVS（更新中）

复现NerfingMVS（更新中）

按以下代码一步步操作 conda create -n NerfingMVS python3.7 conda activate NerfingMVS conda install pytorch1.7.1 torchvision0.8.2 torchaudio0.7.2 -c pytorch pip install -r requirements.txthttps://colmap.github.io/install.html Linux 中 建议的依赖&#xff1…
阅读更多...
AI边缘计算盒子优势有哪些？如何实现低延迟处理？

AI边缘计算盒子优势有哪些？如何实现低延迟处理？

AI边缘计算盒子作为一种集成人工智能技术的边缘计算设备&#xff0c;其优势主要体现在以下几个方面&#xff0c;万物纵横为您详细介绍&#xff1a; 1. 低延迟处理 AI边缘计算盒子靠近数据产生源头&#xff0c;能够即时处理数据&#xff0c;大幅减少数据传输至云端的时间&#…
阅读更多...
深入解析算法效率核心：时间与空间复杂度概览及优化策略

深入解析算法效率核心：时间与空间复杂度概览及优化策略

算法复杂度&#xff0c;即时间复杂度与空间复杂度&#xff0c;衡量算法运行时资源消耗。时间复杂度反映执行时间随数据规模增长的关系&#xff0c;空间复杂度表明额外内存需求。优化策略&#xff0c;如选择合适数据结构、算法改进、循环展开等&#xff0c;对于提升程序效率、减…
阅读更多...
从抖音阳哥的经验看，选品师项目是否值得你投入？

从抖音阳哥的经验看，选品师项目是否值得你投入？

在抖音这个短视频平台上&#xff0c;无数的创作者分享着他们的知识和经验&#xff0c;其中阳哥作为一个备受关注的博主&#xff0c;他的每一次分享都能引起广大网友的热烈讨论。最近&#xff0c;阳哥分享了一个名为“选品师”的项目&#xff0c;让许多对电商和抖音运营感兴趣的…
阅读更多...
RK3576 Android平台SD启动

RK3576 Android平台SD启动

RK3576 Android平台SD启动 要求 1&#xff0c;Android14及以上版本&#xff1b;2&#xff0c;SD卡制作工具&#xff1a;瑞芯微创建升级磁盘工具V1.78及以上版本&#xff1b;3&#xff0c;SD卡容量8G-32G之间&#xff1b; 软件修改 1&#xff0c;Android部分 修改PRODUCT_BO…
阅读更多...
Android 的 Timer 和 TimerTask

Android 的 Timer 和 TimerTask

Timer 简介(来自Gemini) Timer 是 Java 中用于创建定时任务的类。它位于 java.util 包中。可以使用 Timer 来安排一次性或定期执行的任务。 每个 Timer 对象都对应一个后台线程。此线程负责从任务队列中检索任务并按计划执行它们。 使用 Timer 要使用 Timer&#xff0c;首先…
阅读更多...
3D 渲染至少需要多少显存？显存真得越大越好吗？

3D 渲染至少需要多少显存？显存真得越大越好吗？

无论是电影制作、游戏开发还是建筑效果图设计&#xff0c;在今天的计算机图形学领域&#xff0c;都需要强大的图形处理能力。而显存&#xff08;VRAM&#xff09;作为支持这一切的重要组成部分&#xff0c;对于高效3D渲染同样至关重要。在本文中&#xff0c;我们将一起探讨显存…
阅读更多...
Cmake-learning

Cmake-learning

可以把cmake看成一款自动生成 Makefile的工具&#xff0c;所以编译流程就变成了&#xff1a;cmake—>make–>可执行文件 在哪个目录执行cmake txt位置 就会在哪个目录生成构造文件和可执行文件 project(HELLO): 非强制&#xff0c;指明项目名称 add_executable(he…
阅读更多...
【算法】滑动窗口——水果成篮

【算法】滑动窗口——水果成篮

本篇博客是我对“水果成篮”这道题由暴力解法到滑动窗口思路的具体思路&#xff0c;有需要借鉴即可。 目录 1.题目2.暴力求解3.暴力优化3.1每次right不用回退3.2有些left长度一定不如前一个&#xff0c;不用走&#xff0c;left不回退 4.滑动窗口算法5.总结 1.题目 题目链接&am…
阅读更多...
怎么用AI软件设计字体

怎么用AI软件设计字体

一 工具准备 软件&#xff1a;Adobe illustrator 如下网盘自取 链接&#xff1a;https://pan.baidu.com/s/1hlImpN4QlsSkOLLUxINOGA 提取码&#xff1a;love 安装的时候看不全界面&#xff0c;多按几下tab键就能看到按钮。 直接找一款喜欢的字体修改&#xff0c;字体包如下…
阅读更多...
物联网网关制造生产全流程揭秘！

物联网网关制造生产全流程揭秘！

如果您正有开发和定制物联网网关的计划&#xff0c;找一个专业的物联网设备厂商协助您制造生产物联网网关可以节省大量时间和成本&#xff0c;可以让您能专注于当前核心业务&#xff0c;而无需将精力过多地投入到自己不擅长的领域。 当然&#xff0c;了解物联网网关的测试和制…
阅读更多...
基于JSP动漫论坛的设计与实现（二）

基于JSP动漫论坛的设计与实现（二）

目录 3. 系统开发环境及技术介绍 3.1 开发环境 3.2 开发工具 3.2.1 MyEclipse8.5 3.2.2 MySql 3.3 相关技术介绍 3.3.1 JSP技术简介 3.3.2 JDBC技术技术简介 3.3.3 MVC模式与Struts框架技术 4. 总体设计 4.1 系统模块总体设计 4.1.1 普通用户模块设计 4…
阅读更多...
数据库的使用基础-SQL语句

数据库的使用基础-SQL语句

一、在MYSQL中&#xff0c;创建数据库&#xff0c;语法如下&#xff1a; CREATE DATABASE [IF NOT EXISTS] <数据库名> [[DEFAULT] CHARACTER SET <字符集名>] [[DEFAULT] COLLATE <校对规则名>];[ ]中的内容是可选的。语法说明如下&#xff1a; <数据库…
阅读更多...
LeetCode738：单调递增的数字

LeetCode738：单调递增的数字

题目描述 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。 给定一个整数 n &#xff0c;返回 小于或等于 n 的最大数字&#xff0c;且数字呈 单调递增 。 332 代码 class Solution { public:int monotoneIncreasingDigits(…
阅读更多...
Imagine Flash、StyleMamba 、FlexControl、Multi-Scene T2V、TexControl

Imagine Flash、StyleMamba 、FlexControl、Multi-Scene T2V、TexControl

本文首发于公众号&#xff1a;机器感知 Imagine Flash、StyleMamba 、FlexControl、Multi-Scene T2V、TexControl You Only Cache Once: Decoder-Decoder Architectures for Language Models We introduce a decoder-decoder architecture, YOCO, for large language models, …
阅读更多...
QT---day4事件

QT---day4事件

1、思维导图 2、 头文件 #ifndef MYWIDGET_H #define MYWIDGET_H #include <QWidget> #include<QIcon> //图标类 #include<QLabel> //标签类 #include<QMovie> //动图类 #include<QLineEdit> //行编辑器类 #include<QPushButton> //按钮…
阅读更多...
AJAX知识点(前后端交互技术)

AJAX知识点(前后端交互技术)

原生AJAX AJAX全称为Asynchronous JavaScript And XML,就是异步的JS和XML&#xff0c;通过AJAX可以在浏览器中向服务器发送异步请求&#xff0c;最大的优势&#xff1a;无需刷新就可获取数据。 AJAX不是新的编程语言&#xff0c;而是一种将现有的标准组合在一起使用的新方式 …
阅读更多...
【进程等待】阻塞等待 | options非阻塞等待

【进程等待】阻塞等待 | options非阻塞等待

目录 waitpid 阻塞等待 options&非阻塞等待 pid_t返回值 阻塞等待VS非阻塞等待 waitpid 回顾上篇&#xff1a; pid_ t waitpid(pid_t pid, int *status, int options); 返回值&#xff1a; 当正常返回的时候waitpid返回收集到的子进程的进程ID&#xff1b;如果设置了…
阅读更多...
C++容器之vector类

C++容器之vector类

目录 1.vector的介绍及使用1.1vector的介绍1.2vector的使用1.2.1 vector的定义1.2.2 vector iterator 的使用1.2.3 vector 空间增长问题1.2.4 vector 增删查改1.2.5vector 迭代器失效问题1.2.6 vector 在OJ中的使用。 2.vector深度剖析及模拟实现2.1 std::vector的核心框架接口…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站