#先看题目
题目描述
地上有一排格子,共 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→301→2→4→8→16→15→30
第二组样例:
1→2→3→6→12→24→25→501→2→3→6→12→24→25→50
第三组样例:
1→2→4→8→16→32→641→2→4→8→16→32→64
第四组样例:
1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63
请注意在本组样例中,63 不能通过 64−1 得到,因为格子总数为 63 ,没有第 64 个格子。
数据规模与约定
对于 100% 的数据,有 1≤n≤1000000。
题目链接https://www.luogu.com.cn/problem/B3626
#思路
要找最短路所以要用BFS。
#最后附上完整代码
#include<bits/stdc++.h>//万能头文件
using namespace std;
int vis[1000010],n;
queue<int> q;//定义队列
void bfs()
{
memset(vis,-1,sizeof vis);
q.push(1);
vis[1]=0;
while(!q.empty()){//队列不为空就一直执行
int t=q.front();
q.pop();
if(t==n){//因为BFS是按层遍历所有第一次搜出的就是最短路
cout<<vis[n];
return;
}
if(t-1>=1&&t-1<=n&&vis[t-1]==-1){//搜过的地方不重复搜
q.push(t-1);
vis[t-1]=vis[t]+1;
}
if(t+1>=1&&t+1<=n&&vis[t+1]==-1){//注意边界
q.push(t+1);
vis[t+1]=vis[t]+1;
}
if(t*2>=1&&t*2<=n&&vis[t*2]==-1){
q.push(t*2);
vis[t*2]=vis[t]+1;
}
}
return;
}
int main()
{
cin>>n;
bfs();
return 0;//华丽收尾
}