Day-6-广度优先搜索
2023-08-19 15:30:40
发布于：浙江
44阅读
0回复
0点赞
1.
二分前提：具有单调性
int L=初始值,R=初始值,mid;
while(L<=R){
mid=(L+R)/2;//mid=L+(R-L)/2 mid=L+R>>1;
if(条件){
L=mid+1; //R=mid-1
}else{
R=mid-1; //L=mid+1
}
}
2.
广搜：解决最小步数
void bfs(){
1.定义一个队列 思考：队列应该是什么类型？
2.起点入队
3.标记起点 思考：vis 是1维数组，2维数组
4.
while(队列不为空){
5.获取队首元素t
6.队首元素出队
7.判断队首是否到达终点{
//输出处理结果
return;
}
8.用队首元素t拓展新结点{
新结点合法
入队
标记新结点
}
}
}
#include<bits/stdc++.h>
using namespace std;
int n,k;
int vis[100005];
struct node{
int y,step;//走到y的步数
};
void bfs(){
queue<node> q;
node n1={n,0};
q.push(n1);
vis[n]=1;//标记起点
while(!q.empty()){
node t=q.front();
q.pop();
if(t.y==k){
cout<<t.step;
return;
}
//没有到达终点
int ny1=t.y+1;
if(ny1<=100000 &&vis[ny1]==0){
q.push({ny1,t.step+1});
vis[ny1]=1;
}
//-1
int ny2=t.y-1;
if(ny2>=0 && vis[ny2]==0){
q.push({ny2,t.step+1});
vis[ny2]=1;
}
int ny3=t.y*2;
if(ny3<=100000 && vis[ny3]==0){
q.push({ny3,t.step+1});
vis[ny3]=1;
}
}
}
int main(){
cin>>n>>k;
bfs();
return 0;
}
#include<iostream>
#include<queue>
using namespace std;
int n,a,b,v[205],vis[205];//n表示房间数，a和b分别表示起点和终点
struct node{
int room,step;
};
void bfs(){
//1.定义一个队列
queue<node> q;
//2.起点入读
q.push({a,0}); //起点为a，步数为0
//3.标记起点
vis[a]=1;
//4.
while(!q.empty()){ //
//5.获取队首
node t=q.front();
q.pop();
//6.判断队首是否到达终点
if(t.room==b){
cout<<t.step;
return;
}
//7.用队首取拓展新结点 t.room+v[t.room] t.room-v[t.room]
int tt1=t.room+v[t.room];
if(tt1>=1 && tt1<=n && !vis[tt1]){
q.push({tt1,t.step+1});
vis[tt1]=1;
}
int tt2=t.room-v[t.room];
if(tt2>=1 && tt2<=n && !vis[tt2]){
q.push({tt2,t.step+1});
vis[tt2]=1;
}
}
cout<<-1;
}
int main(){
freopen("bear.in","r",stdin);
freopen("bear.out","w",stdout);
cin>>n>>a>>b;
for(int i=1;i<=n;i++){
cin>>v[i];
}
bfs();
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个