把远古集训营题解亮一下
2024-08-25 17:00:38
发布于:上海
8阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,k,vis[1000005];
struct node{
int x,step;//位置,步数
};
void bfs(){
queue<node> q;
q.push({n,0});
vis[n]=1;//标记
while(q.size()){
node n1=q.front();
q.pop();
//判断队首是否到达终点
if(n1.x==k){
// 输出步数
cout<<n1.step;
return;
}
//用n1点去拓展新的结点 n1.x +1 -1 n1.x*2
//+1
if(n1.x+1<=100000 && n1.x+1>=0 && vis[n1.x+1]==0){
//标记n1.x+1 ,q.push({n1.x+1,n1.step+1});
vis[n1.x+1]=1;
q.push({n1.x+1,n1.step+1});
}
//-1
// if(n1.x-1在界内 并且n1.x-1没走过) 标记n1.x-1 ,q.push({n1.x-1,n1.step+1});
if(n1.x-1>=0 && n1.x-1<=100000 && vis[n1.x-1]==0){
vis[n1.x-1]=1;
q.push({n1.x-1,n1.step+1});
}
//*2
// if(n1.x*2在界内 并且n1.x*2没走过) 标记n1.x*2 ,q.push({n1.x*2,n1.step+1});
if(n1.x*2>=0 && n1.x*2<=100000 && vis[n1.x*2]==0){
vis[n1.x*2]=1;
q.push({n1.x*2,n1.step+1});
}
}
}
int main(){
//n k
cin>>n>>k;
bfs();
return 0;
}
这里空空如也
有帮助,赞一个