```cpp
#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
int vis[100005];
struct node
{
int x;
int step;
};
node s;
queue<node> q;
void bfs()
{
q.push(s);
while(!q.empty())
{
node tmp=q.front();
q.pop();
if(tmp.x==m)
{
cout<<tmp.step;
return;
}
node a=tmp;
a.x++;
a.step++;
if(vis[a.x]==0&&a.x<=100000)
{
q.push(a);
vis[a.x]=1;
}
a.x-=2;
if(vis[a.x]==0&&a.x<=100000)
{
q.push(a);
vis[a.x]=1;
}
a.x++;
a.x*=2;
if(vis[a.x]==0&&a.x<=100000)
{
q.push(a);
vis[a.x]=1;
}
}
}
int main()
{
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n>>m;
}
s.x=n;
s.step=0;
bfs();
return 0;
}
```
刚才忘记标记了,但是还是RE
by shooting__star @ 2024-02-11 15:18:21
@[shooting__star](/user/955954) 你可以问问 @[sz_mane](/user/743373) 。
by xk2013 @ 2024-02-11 15:27:46
@[shooting__star](/user/955954) 你的bfs调用应该在每次for里面啊
by ljlbj_fengyuwuzu @ 2024-02-11 15:29:17
@[shooting__star](/user/955954) 然后,每次把队首取出来之后vis应该标记为false
by ljlbj_fengyuwuzu @ 2024-02-11 15:31:30
@[shooting__star](/user/955954) 倒退时会出现负数情况,你的判断边界就不再是`a.x<=100000`了
by Special_Tony @ 2024-02-11 15:33:08
@[shooting__star](/user/955954) My AC code:
```cpp
# include <bits/stdc++.h>
# define old_six \
ios::sync_with_stdio (0);\
\
cin.tie (0);\
\
cout.tie (0);
# define ffor(i,name) \
for (auto i = name.begin (); i != name.end (); ++ i)
# define iter(type) \
type :: iterator
# define reg register
# define inl inline
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
int t, x, y, maxn, a[3];
bool vis[200005];
int bfs () {
queue <pii> q;
q.push ({x, 0});
vis[x] = 1;
while (! q.empty ()) {
pii x = q.front ();
// cout << x.second << ':' << x.first << '\n';
if (x.first == y)
return x.second;
q.pop ();
a[0] = x.first - 1;
a[1] = x.first + 1;
a[2] = x.first << 1;
for (reg int i = 0; i < 3; ++ i)
if (~a[i] && a[i] < maxn && ! vis[a[i]])
q.push ({a[i], x.second + 1}), vis[a[i]] = 1;
}
// return -1;
}
int main () {
old_six
cin >> t;
while (t --) {
cin >> x >> y;
if (y < x) {
cout << x - y << '\n';
continue ;
}
maxn = y * 2;
memset (vis, 0, sizeof vis);
cout << bfs () << '\n';
}
return 0;
}
```
by Special_Tony @ 2024-02-11 15:33:52
@[sz_mane](/user/743373) %%%
by ljlbj_fengyuwuzu @ 2024-02-11 15:36:03
深搜挂了,,,
by ljlbj_fengyuwuzu @ 2024-02-11 15:40:49
@[shooting__star](/user/955954)
数组开小了,开到两万零几就可以了
by zcy6666666 @ 2024-02-15 10:21:29
@[shooting_star](https://www.luogu.com.cn/user/955954#main)你的队列没有清空而且要循环bfs();先附上我的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,st,ed,ans;
bool vis[100005];
struct node{
int x,s;
};
void bfs(){
queue<node>que;
que.push({st,0});
vis[st]=1;
while(!que.empty()){
auto q1=que.front();
que.pop();
if(q1.x==ed){
ans=q1.s;
return;
}
int l=q1.x-1;
int r=q1.x+1;
int s=q1.x*2;
if(l>=0&&!vis[l]){
que.push({l,q1.s+1});
vis[l]=1;
}if(r<=1e5&&!vis[r]){
que.push({r,q1.s+1});
vis[r]=1;
}if(s<=1e5&&!vis[s]){
que.push({s,q1.s+1});
vis[s]=1;
}
}
}
int main(){
cin>>t;
while(t--){
cin>>st>>ed;
memset(vis,0,sizeof(vis));
bfs();
cout<<ans<<endl;
}
return 0;
}
```
保证已AC
by shiliuhaoyu @ 2024-02-19 10:18:26