jzoj中的抓住那头牛---------c++

哟，我的第二个作品

问题 A: 抓住那头牛

时间限制: 1.000 Sec  内存限制: 128 MB
提交: 401  解决: 353
[命题人:][下载数据: ?]

提交状态报告

题目描述

一天，农夫John听说有一头奶牛逃跑了，他想立刻抓住这只逃跑的奶牛。John的起始位置为数轴上的点N(0 ≤ N ≤ 100,000)，而奶牛的位置则为这条数轴上的点K(0 ≤ K ≤ 100,000)，John有两种移动方式：
*步行：花一分钟的时间从点x移动至点x+1或点x-1；
*瞬间移动：花一分钟的时间从点x移动至点2*x。
如果奶牛没有意识到John的追赶，而停在原地不动，那么John最少要花多少时间才能抓住这只奶牛？要求：农夫只能在0..100000位置范围内移动。

输入

一行两个整数：n和k。

输出

一行一个整数，表示农夫John抓到这头奶牛所花的最少时间（单位：分钟）；

样例

输入  复制

5 17

输出  复制

4

提示

5-10-9-18-17，共计4分钟。

看样子使用c++bfs做

...c++

#include<bits/stdc++.h>
using namespace std;
int catchCow(int n,int k)
{if (n==k){return 0;}vector<int> visited(100001,-1);queue<int> q;q.push(n);visited[n]=0; while (!q.empty()){int current = q.front();q.pop();if (current==k){return visited[current];}if (current-1>=0&&visited[current-1]==-1){q.push(current-1);visited[current-1]=visited[current]+1;}if (current+1<=100000&&visited[current+1]==-1){q.push(current+1);visited[current+1]=visited[current]+1;}if (current*2<=100000&&visited[current*2]==-1){q.push(current*2);visited[current*2]=visited[current]+1;}}return -1;
}
int main()
{int n, k;cin >> n >> k;int result=catchCow(n, k);cout<<result<<endl;return 0;
}