本题知识点:宽度优先搜索
题意很简单,我们把FJ与奶牛看作是在一条数轴上的点,奶牛固定在K点,FJ的移动有三种,分别是向前一格,向后一格以及跳到当前格的两倍去。问FJ花费最少的时间到达奶牛的点。
这题当意识到他们在数轴上时,结合bfs的思想就很快可以解决了。
数据很小。
// POJ 3278
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int N, K;
bool take[100005];
int len[100005];
queue<int> que;
void bfs(){
len[N] = 0;
take[N] = true;
que.push(N);
while(!que.empty()){
int now = que.front(); que.pop();
if(now == K) break;
// 跳到 K 的后面就可以 -1 了
if(now * 2 <= K + 1 && !take[now * 2]){
len[now * 2] = len[now] + 1;
take[now * 2] = true;
que.push(now * 2);
}
if(now + 1 <= K + 1 && !take[now + 1]){
len[now + 1] = len[now] + 1;
take[now + 1] = true;
que.push(now + 1);
}
if(now - 1 >= 0 && !take[now - 1]){
len[now - 1] = len[now] + 1;
take[now - 1] = true;
que.push(now - 1);
}
}
}
int main()
{
scanf("%d %d", &N, &K);
bfs();
printf("%d\n", len[K]);
return 0;
}