抓住那头牛
题目 抓住那头牛
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟 从 X 移动到 2∗X，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。
农夫 最少 要花多少时间才能抓住牛？
输入格式 共一行，包含两个整数N和K。
输出格式 输出一个整数，表示抓到牛所花费的 最少时间 。
数据范围 0≤N,K≤105
输入样例：
5 17
输出样例：
4
思路分析
当时看到这题感觉是dp的题 但确实是bfs更好做
又细想了一下区别
好像是一种 每个点都有相同选择的递归模型
这要是放在dfs里面 就是指数型枚举了 然后dp的入门题，跳台阶也是这种类型 指数型枚举进行剪枝，记忆化搜索，然后省去递直接推，逐步优化成dp 好像串起来了
但是有什么区别呢 貌似dfs和dp求的是方案数 而bfs求的是达到某个状态的最少需要的次数 其实dp也能做这件事吧 但是bfs自然适应这种场景的特性 解决起来更为直观且高效
对于这个特定问题，用宽度优先搜索（BFS）通常比动态规划（DP）更高效。原因如下：
- 直接寻找最短路径：BFS直接以层级形式扩散搜索，确保找到的第一个解就是最优解，即最短时间。一旦找到目标，搜索即停止。
- 避免不必要的计算：BFS在寻找过程中，一旦一个节点被访问，其到起点的最短路径就被确定，不需要重复计算。而DP可能需要计算多条路径到达同一点的情况，尤其是在这个问题的设置中，很多路径可能根本不会被采用。
- 空间优化：虽然BFS需要存储当前层的所有节点，但对于这个问题，空间消耗是可控的，特别是考虑到题目给定的数据范围。而DP可能需要一个大数组来存储到每个点的最短时间，尽管在实际操作中这也是可行的。
然而，如果问题变得更加复杂，例如，如果牛也在移动，或者有更复杂的移动规则，动态规划可能就更有优势了，因为它能够更好地处理这种复杂性。动态规划的优势在于它的通用性和对于复杂问题的适应能力，尤其是当问题具有明确的最优子结构和重叠子问题时。
总的来说，对于这个简单的追赶问题，BFS因为其简洁和高效，通常是更好的选择。但DP在处理更复杂或需要找到所有可能解的问题时展现出其强大的能力。在选择算法时，理解问题的本质和算法的特性是关键。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=2e5+10;
int n,k;
int d[N];
bool isVaild(int x){
return x>=0 && x<=N && d[x]==-1;
}
void bfs(int x){
queue<int> q;
memset(d,-1,sizeof d);
q.push(x);
d[x]=0;
while(q.size()){
int cur=q.front();q.pop();
if(cur==k){
cout<<d[k];
return;
}
int choice1=cur+1,choice2=cur-1,choice3=cur*2;
if(isVaild(choice1)){
d[choice1]=d[cur]+1;
q.push(choice1);
}
if(isVaild(choice2)){
d[choice2]=d[cur]+1;
q.push(choice2);
}
if(isVaild(choice3)){
d[choice3]=d[cur]+1;
q.push(choice3);
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
bfs(n);
return 0;
}
💬 评论