这是我的代码,应该是可以算出正确答案的,但是提交后一直显示超时,我剪枝了很多地方可还是通过不了,真的很不理解!!
我用的是bfs,分支限界法,还用了queue
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int N; //农夫的位置,范围0~1000,000
int K; //牛的位置,范围0~1000,000
int bestlen; //最远走到的位置
bool yet[1000010]; //已走过的位置赋值为true,便于剪枝
int Count[1000010] = { 0 }; //记录每一步的步数
queue<int>open; //open表,一层一层存储,死节点
queue<int>close; //close表,扩展节点
int best = 0; //存放最优解
void BFS() {
while (true) {
int num = close.front(); //num用于记录当前扩展结点的值
int num_a; //num_a用于记录当前扩展结点的子节点
for (int i = 1; i <= 3; i++) { //农夫有三种移动可能
switch (i) {
case 1: //农夫移动方式为X-1
num_a = num - 1;
if (!yet[num_a] && num_a >= 0 && num_a < bestlen && Count[num_a] <= abs(N - K)) { //剪枝
close.push(num_a); //子节点满足条件则放在close表最后
Count[num_a] = Count[num] + 1; //步数加1,即层数加1
yet[num_a] = true; //记录已走过的位置,置为true
if (close.back() == K) { //找到最优解
best = Count[close.back()]; //将最优解记录下来
return; //找到最优解退出函数
}
}
break;
case 2: //农夫移动方式为X+1
num_a = num + 1;
if (!yet[num_a] && num_a <= 1000000 && num_a < bestlen && Count[num_a] <= abs(N - K)) {
close.push(num_a);
Count[num_a] = Count[num] + 1; //步数加1
yet[num_a] = true; //记录已走过的位置
if (close.back() == K) { //找到最优解
best = Count[close.back()];
return ;
}
}
break;
case 3: //农夫移动方式为X*2
num_a = num * 2;
if (!yet[num_a] && num_a <= 1000000 && num_a < bestlen && Count[num_a] <= abs(N - K)) {
close.push(num_a);
Count[num_a] = Count[num] + 1; //步数加1
yet[num_a] = true; //记录已走过的位置
if (close.back() == K) { //找到最优解
best = Count[close.back()];
return ;
}
}
break;
}
}
open.push(close.front());
close.pop();
}
}
int main() {
memset(yet, false, sizeof(open)); //将yet数组的元素都初始化为false
cin >> N >> K;
close.push(N); //将农夫的位置放在close表中
yet[N] = true; //将农夫的位置赋值为true,表示此位置不可重复走
bestlen = K + abs(N - K); //初始化最远长度
BFS(); //广度优先搜索
cout << best << endl; //输出最优解
return 0;
}