样例不对
查看原帖
样例不对
957610
dinghansun楼主2024/7/20 16:42

bfs,输出为6???

#include<bits/stdc++.h>
using namespace std;
int t,x,y,ans;
bool f[100001];
int step[100001];
void bfs(){
	queue<int> q;
	q.push(x);
	step[x]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(f[u]) continue;
		if(u==y) return;
		else{
			if(u+1<=100000&&!f[u+1]){
				q.push(u+1);
				step[u+1]=step[u]+1;
			}
			if(u-1>=1&&!f[u+1]){
				q.push(u-1);
				step[u-1]=step[u]+1;
			}     
			if(2*u<=200000&&!f[2*u]){
				q.push(2*u);
				step[u*2]=step[u]+1;
			}
			f[u]=true;
		}
	}
}
int main()
{
	cin>>t;
	for(int z=1;z<=t;z++){
		cin>>x>>y;
		bfs();
		cout<<step[y]<<endl;
		memset(f,0,sizeof(f));
		memset(step,0,sizeof(step));
	}
	return 0;
}

2024/7/20 16:42
加载中...