这题dp就行了
by SandWave2023 @ 2023-09-05 18:03:27
@[HuangDER](/user/857173) 虽然但是,我想练一下广搜 (
by A_R_O_N_A @ 2023-09-05 18:16:05
@[xie_T34](/user/846661)
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
static int sta[35];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top)putchar(sta[--top]+'0');
}
queue<int>q;
int t,x,y,mp[100005];
bool vis[100005]={false};
void bfs(){
while(!q.empty()){
int now=q.front();
vis[now]=true;
q.pop();
if(now-1>=1&&!vis[now-1]){
q.push(now-1);
mp[now-1]=min(mp[now-1],mp[now]+1);
}
if(now+1<=100001&&!vis[now+1]){
q.push(now+1);
mp[now+1]=min(mp[now+1],mp[now]+1);
}
if(now*2<=100001&&!vis[now*2]){
q.push(now*2);
mp[now*2]=min(mp[now*2],mp[now]+1);
}
}
}
int main(){
t=read();
while(t--){
memset(mp,0x3f,sizeof(mp));
memset(vis,0,sizeof(vis));
while(!q.empty())q.pop();
x=read();
y=read();
q.push(x);
mp[x]=0;
bfs();
write(mp[y]);
puts("");
}
return 0;
}
```
宽搜改成上面这样就行,改了两个地方,因为题目中的要求是求最小步数所以我们每次更新点的答案的时候要与原来的值取 $min$,所以第二处改动为一开始给 $mp$ 数组赋初值的时候要赋值为无穷大,然后给起点的 $mp$ 赋值为 $0$ ,类似最短路算法的赋值。
~~求关~~
by VIOLET__FOREVER @ 2023-09-05 18:27:51
@[VIOLET__FOREVER](/user/422387) 谢大佬,已关
by A_R_O_N_A @ 2023-09-06 09:38:04