4001:抓住那头牛 查看提交统计提示提问 总时间限制: 2000ms 内存限制: 65536kB 描述 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟 2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入 两个整数，N和K 输出 一个整数，农夫抓到牛所要花费的最小分钟数 样例输入 5 17 样例输出 4
/* 抓住那头牛 思路，利用广搜逐步扩展节点 */ #include<iostream> #include<cstring> #include<queue> using namespace std; int N,K; const int MAXN = 100000; int visited[MAXN + 10]; struct Step{ int x; //位置 int steps; //走到x所需的步数 Step(int xx,int s):x(xx),steps(s) { } }; queue<Step> q; int main() { cin >> N >> K; memset(visited,0,sizeof(visited)); q.push(Step(N,0)); visited[N] = 1; while(!q.empty()){ Step s = q.front(); if(s.x == K){ cout << s.steps << endl; return 0; } else{ if(s.x - 1 >= 0 && !visited[s.x - 1]){ q.push(Step(s.x- 1,s.steps + 1)); visited[s.x - 1] = 1; } if(s.x + 1 <= MAXN && !visited[s.x + 1]){ q.push(Step(s.x+ 1,s.steps + 1)); visited[s.x + 1] = 1; } if(s.x * 2 <= MAXN && !visited[s.x * 2]){ q.push(Step(s.x * 2,s.steps + 1)); visited[s.x * 2] = 1; } q.pop(); } } return 0; }