题目描述
农夫和牛都位于数轴上,农夫起始位于点 N ,牛位于点 K 。
农夫有两种移动方式:
从 X 移动到 X−1 或 X+1 ,每次移动花费一分钟
从 X 移动到 2∗X ,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。
农夫最少要花多少时间才能抓住牛?
输入格式
共一行,包含两个整数N和K。
输出格式
输出一个整数,表示抓到牛所花费的最少时间。
数据范围
0≤N,K≤105
样例
输入样例:
5 17
输出样例:
4
算法
广度优先搜索(深度优先搜索)
bfs:
特判:若终点小于起点只有倒退一种走法,直接输出差值。
常规:开两队列,分别储存到达的点和最短到达的时间。
(可用book数组记录访问过的值,避免一个数被重复压入队列)
dfs:
同理上。
此题上性能不如bfs好,故不推荐。
C++ 代码
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
int g[100010]={};
int check(int x,int y){//两种情况判断
if(x==1) return x;
return y;
}
void bfs(){
queue<int> ans;
queue<int> qx;
qx.push(n);
ans.push(0);
while(!qx.empty()){
for(int i=1;i<=2;i++){
int tx=qx.front()+check(i,qx.front());
if(tx>=0 && tx<m){//判断边界
qx.push(tx);//满足就压入
ans.push(ans.front()+1);
}
if(tx==m){//到达终点直接输出并返回
int k=ans.front()+1;
cout<<k;//输出结果
return;
}
}
qx.pop(),ans.pop();
}
}
int main(){
cin>>n>>m;
if(m<=n) cout<<n-m;//首先特判起点和终点我位置关系,先解决起点小于终点的简单情况
else bfs();
return 0;
}
然而 DFS 可以记忆化…
orz%%%