当前位置：首页 > news >正文

双向BFS

news 2025/6/23 22:19:06

1034 Number Game
分数 35
作者陈越
单位浙江大学
A number game is to start from a given number A, and to reach the destination number B by a sequence of operations.

For the current number X, there are 3 types of operations:

X=X+1
X=X−1
X=X×N
Your job is to find the minimum number of steps required to reach B from A.

Input Specification:
Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, three integers are given: A, B and N, where −10
5
≤A,B≤10
5
and 1<N<10. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in a line the minimum number of steps required to reach B from
创建两个队列和两个哈希表

queue<string> que1;
queue<string> que2;
unordered_map da<string,int> da1;
unordered_map db <string,int> db2;

(25)分双向bfs
还能怎么优化呢？请赐教

#include <bits/stdc++.h>
using namespace std;
const int K = 20;
int k;int extend(queue<int>& que,int N,map<int,int>& set_1,map<int,int>& set_2,bool temp,int d){int len = que.size();int ans = 0xffffffff;while(len--){int top  = que.front();que.pop();if(set_1.find(top+1) == set_1.end()){set_1[top+1] = d;que.push(top+1);if(set_2.find(top+1) != set_2.end()){ans = max(d + set_2[top+1],ans);}}if(set_1.find(top-1) == set_1.end()){set_1[top-1] = d;que.push(top-1);if(set_2.find(top-1) != set_2.end()){ans = max(d+set_2[top-1],ans);}}if(temp == true){if(set_1.find(top*N) == set_1.end()){set_1[top*N] = d;que.push(top*N);if(set_2.find(top*N) != set_2.end()){ans = min(set_2[top*N] + d,ans);}}}else{if(N != 0 && top % N == 0){if(set_1.find(top/N) == set_1.end()){set_1[top/N] = d;que.push(top/N);if(set_2.find(top/N) != set_2.end()){ans = min(set_2[top/N]+d,ans);}}}}}return ans;
}
int bfs(int s,int e,int n){queue<int> que1;queue<int> que2;map<int,int> set1;map<int,int> set2;que1.push(s);set1[s] = 0;que2.push(e);set2[e] = 0;if(s == e){return 0;}int d1 = 0;int d2 = 0;while(que1.size() && que2.size()){if(que1.size() < que2.size()){d1++;int t = extend(que1,n,set1,set2,true,d1);if(t != 0xffffffff){//cout<<d1<<" "<<d2<<endl;return t;}}else{d2++;int t = extend(que2,n,set2,set1,false,d2);if(t != 0xffffffff){// cout<<d1<<" "<<d2<<endl;return t;}}}return -1;
}
int main(){cin>>k;while(k--){int s,e,n;cin>>s>>e>>n;int a = bfs(s,e,n);cout<<a<<endl;}
}