本文主要是介绍B3626 跳跃机器人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
地上有一排格子，共 n 个位置。机器猫站在第一个格子上，需要取第 n 个格子里的东西。
机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：
- 初始时，机器人位于 1 号格子
- 若机器人目前在 x 格子，那么它可以跳跃到 x−1,x+1,2x 里的一个格子（不允许跳出界）
问机器人最少需要多少次跳跃，才能到达 n 号格子。
输入格式
仅一行，一个正整数，表示 n。
输出格式
仅一行，一个正整数，表示最少跳跃次数。
输入输出样例
输入 #1
30
输出 #1
6
输入 #2
50
输出 #2
7
输入 #3
64
输出 #3
6
输入 #4
63
输出 #4
8
说明/提示
样例解释
第一组样例：
1→2→4→8→16→15→30
第二组样例：
1→2→3→6→12→24→25→50
第三组样例：
1→2→4→8→16→32→64
第四组样例：
1→2→4→8→16→32→31→62→63
请注意在本组样例中，63 不能通过 64−1 得到，因为格子总数为 63，没有第 64 个格子。
数据规模与约定
对于 100% 的数据，有 1≤n≤1000000。
思路
用BFS做，分为队列和结构体两种解法。
完整代码
队列：
#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int> >pt;
bool v[1000001];
int n;
void bfs(int a){pt.push(make_pair(1,0));v[1]=true;while(!pt.empty()){int p=pt.front().first;int t=pt.front().second;pt.pop();if(p==a){cout<<t;//freopen("b.out","w",stdout);return;}if(p-1>=1&&!v[p-1]){v[p-1]=true;pt.push(make_pair(p-1,t+1));}if(p+1<=n&&!v[p+1]){v[p+1]=true;pt.push(make_pair(p+1,t+1));}if(p*2<=n&&!v[p*2]){v[p*2]=true;pt.push(make_pair(p*2,t+1));}}
}
int main(){cin>>n;//freopen("a.in","r",stdin);bfs(n);return 0;
}结构体+队列：
#include<bits/stdc++.h>//T2-2
using namespace std;
struct node{int l,ans;
};
queue<node> q;
int n,vis[1000010];
int main(){q.push({1,0});cin>>n;while(!q.empty()){node t=q.front();q.pop();if(vis[t.l])continue;vis[t.l]=1;if(t.l<=0||t.l>n)continue;if(t.l==n){cout<<t.ans;return 0;}int d1=t.l-1,d2=t.l+1,d3=t.l*2;if(d1>1&&d1<=n&&vis[d1]==0){q.push({d1,t.ans+1});}if(d2>1&&d2<=n&&vis[d2]==0){q.push({d2,t.ans+1});}if(d3>1&&d3<=n&&vis[d3]==0){q.push({d3,t.ans+1});}}return 0;
}这篇关于B3626 跳跃机器人的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
