【题解-洛谷】B3626 跳跃机器人
题目：B3626 跳跃机器人
题目描述
地上有一排格子，共 n n n 个位置。机器猫站在第一个格子上，需要取第 n n n 个格子里的东西。
机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：
- 初始时，机器人位于 1 1 1 号格子
- 若机器人目前在 x x x 格子，那么它可以跳跃到 x − 1 , x + 1 , 2 x x-1, x+1, 2x x−1,x+1,2x 里的一个格子（不允许跳出界）
问机器人最少需要多少次跳跃，才能到达 n n n 号格子。
输入格式
仅一行，一个正整数，表示 n n n。
输出格式
仅一行，一个正整数，表示最少跳跃次数。
输入输出样例 #1
输入 #1
30
输出 #1
6
输入输出样例 #2
输入 #2
50
输出 #2
7
输入输出样例 #3
输入 #3
64
输出 #3
6
输入输出样例 #4
输入 #4
63
输出 #4
8
说明/提示
样例解释
第一组样例：
1 → 2 → 4 → 8 → 16 → 15 → 30 1\to 2 \to 4\to 8 \to 16 \to 15 \to 30 1→2→4→8→16→15→30
第二组样例：
1 → 2 → 3 → 6 → 12 → 24 → 25 → 50 1\to 2\to 3\to6\to12\to24\to25\to 50 1→2→3→6→12→24→25→50
第三组样例：
1 → 2 → 4 → 8 → 16 → 32 → 64 1\to 2\to4\to8\to16\to32\to64 1→2→4→8→16→32→64
第四组样例：
1 → 2 → 4 → 8 → 16 → 32 → 31 → 62 → 63 1\to 2\to4\to8\to16\to32\to31\to62\to63 1→2→4→8→16→32→31→62→63
请注意在本组样例中， 63 63 63 不能通过 64 − 1 64-1 64−1 得到，因为格子总数为 63 63 63，没有第 64 64 64 个格子。
数据规模与约定
对于 100 % 100\% 100% 的数据，有 1 ≤ n ≤ 1000000 1\leq n \leq 1000000 1≤n≤1000000。
代码
#include<iostream>
#include<cstring>using namespace std;const int Maxn = 1000000 + 10;int n, d[Maxn], hh, tt = -1, q[Maxn];void insert(int x){q[++ tt] = x;
}void dele(){hh ++;
}bool isempty(){return hh > tt;
}int bfs(){memset(d, -1, sizeof d);insert(1);d[1] = 0;int dx[3] = {-1, 1, 2};while(!isempty()){int t = q[hh];dele();for(int i = 0; i < 3; i ++){int newx;if(i < 2){newx = t + dx[i];}else{newx = t * dx[i];}if(newx >= 1 && newx <= n && d[newx] == -1){insert(newx);d[newx] = d[t] + 1;}if(newx == n){return d[newx];}}}
}int main(){scanf("%d", &n);int res = bfs();printf("%d", res);return 0;
}
结果
