题目描述
从一个点到另一个点的步数
输入样例
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;
}
}
如何理解第一次走到不一定是最小值???
第一次走到一定最小,所以flag[xx]>flag[f.x]+1这步不用的
大佬强啊
sto
棒啊