【题解-洛谷】B3626 跳跃机器人

题目：B3626 跳跃机器人

题目描述

地上有一排格子，共 $n$ 个位置。机器猫站在第一个格子上，需要取第 $n$ 个格子里的东西。

机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：

• 初始时，机器人位于 $1$ 号格子
• 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x-1,x+1,2x$ 里的一个格子（不允许跳出界）

问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。

输入格式

仅一行，一个正整数，表示 $n$。

输出格式

仅一行，一个正整数，表示最少跳跃次数。

输入输出样例 #1

输入 #1

30

输出 #1

6

输入输出样例 #2

输入 #2

50

输出 #2

7

输入输出样例 #3

输入 #3

64

输出 #3

6

输入输出样例 #4

输入 #4

63

输出 #4

8

说明/提示

样例解释

第一组样例：
$1\to 2\to 4\to 8\to 16\to 15\to 30$

第二组样例：
$1\to 2\to 3\to 6\to 12\to 24\to 25\to 50$

第三组样例：
$1\to 2\to 4\to 8\to 16\to 32\to 64$

第四组样例：
$1\to 2\to 4\to 8\to 16\to 32\to 31\to 62\to 63$

请注意在本组样例中，$63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 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;
}

结果