题目描述

从一个点到另一个点的步数

输入样例

5 17

输出样例

4

分析

假设位置为x
1.只能跳到2*x或者 x+1 ，x-1，也就是说只要n>k就只能向后跳（特判）
2.跳的方向设定为 dx[3]={1,-1,x},而如果跳到的位置大于2*k其实是
完全没有必要的，因为那样的话就必须一步一步在跳回来

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int flag[200100];
int n,k;
struct edge {
    int x;
} adj;
queue<edge>q;
int main() {
    memset(flag,-1,sizeof(flag));
    cin>>n>>k;
    if (k<=n) {
        cout<<n-k;
        return 0;
    } else {
        int a;
        adj.x=n;
        flag[n]=0;
        q.push(adj);
        while(!q.empty()) {
            edge f=q.front();
            a=f.x;
            int dx[3]= {1,-1,a};
            q.pop();
            for (int i=0; i<3; i++) {
                int xx=f.x+dx[i];
                if (xx>=1&&xx<=2*k&&(flag[xx]==-1||flag[xx]>flag[f.x]+1)) {
                    flag[xx]=flag[f.x]+1;
                    adj.x=xx;
                    q.push(adj);
                }
            }
        }
        cout<<flag[k];
        return 0;
    }
}