地址 https://www.acwing.com/problem/content/description/1102/
农夫知道一头牛的位置,想要抓住它。 农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。 农夫有两种移动方式: 从 X 移动到 X−1 或 X+1,每次移动花费一分钟 从 X 移动到 2∗X,每次移动花费一分钟 假设牛没有意识到农夫的行动,站在原地不动。 农夫最少要花多少时间才能抓住牛? 输入格式 共一行,包含两个整数N和K。 输出格式 输出一个整数,表示抓到牛所花费的最少时间。 数据范围 0≤N,K≤105 输入样例: 5 17 输出样例: 4
解答
算法1
常规BFS 需要注意的是x=x2需要进行限制否则会向不可能得到答案的方向不断增长
x=x2 必须小于 2*k
// 11123.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <queue> #include <set> using namespace std; int n, m; set<int> vis; int main() { cin >> n >> m; queue<pair<int, int>> q; q.push({ n,0 }); vis.insert(n); if (m <= n) { cout << n - m; return 0; } while (q.size()) { int t = q.front().first; int step = q.front().second; q.pop(); int next1 = t - 1; int next2 = t + 1; int next3 = t * 2; if (next1 == m || next2 == m || next3 == m) { cout << step + 1 << endl; return 0; } if(vis.count(next1) == 0){ q.push({ next1,step + 1 }); vis.insert(next1); } if ( vis.count(next2) == 0) { q.push({ next2,step + 1 }); vis.insert(next2); } if( next3 < 2*m && vis.count(next3) == 0){ q.push({ next3,step + 1 }); vis.insert(next3); } } return 0; }