每次移动可以向前一步，向后一步，或飞跃到当前坐标两倍的位置，求找到奶牛所需要的最少步数。
这道题很适合bfs入门，三种情况看做一棵树的三个子节点，那么从起点开始，可以简单画个图：
假如我们要找的奶牛在点12：
如果是是深度优先遍历(DFS)，我们需要依次查询A14...A15...A16...找遍A1的所有后续序列后，再找A2，A3，直到找到12；
而广度优先遍历的做法(BFS)，是先查询A，然后查询123，再查询 456 789 101112，三次查询就能找到目标点12；
两种查询方式有什么算法效率上的优劣呢？
DFS 适合深度较大，分支较少的树，查找难度随着分支增加而增大；
BFS 适合深度较浅，分支较多的树，查询难度随着深度增加而增大；
像奶牛这道题，奶牛的活动范围是1~10^6，求出从起点到奶牛位置最少需要几步。
如果用DFS，每次查询可能需要遍历所有10^6个点，由于需要找到最小步数，即使剪枝也很难有较高的效率；（实际上这道题用DFS需要反过来从终点找起点，再讨论查找方式）
而BFS找到的第一个点就是到达目标点所需要的最小步数。
BFS的代码算法是基于队列的 C++ STL中栈和队列的使用方法
还是这张图：
第一次把A放入队首，查询是否为目标点；
抛出队首元素，然后将三个子节点1 2 3放入队列，对队列中剩余的三个点查询；
抛出队首的1，然后将1 的子节点4 5 6放入队列，查询；
抛出队首的2，然后将2 的子节点7 8 9放入队列，查询；
抛出队首的3，然后将3 的子节点10 11 12放入队列，查询，查询到目标点12，结束。
代码部分：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
#define maxn 100001
int vis[maxn],step[maxn];
queue<int >q; //定义全局队列
int bfs(int n,int m)
{
int head,next;
q.push(n);
step[n]=0;
vis[n]=1;
while(!q.empty()) //队列不为空则一直循环
{
head=q.front(); //获取队首元素，然后弹出
q.pop();
for(int i=1;i<=3;i++) //3种前进方式
{
if(i==1)
next=head-1;
else if(i==2)
next=head+1;
else
next=head*2;
if(next<0||next>=maxn) //判断是否越界
continue;
if(!vis[next]) //判断是否已经来过该点
{
q.push(next); //将子节点插入队尾
step[next]=step[head]+1; //步数加 1
vis[next]=1; //标记已经来过的点
}
if(next==m) //找到目标点
return step[next];
}
}
}
int main()
{
int n,m;
mem(vis,0);
while(!q.empty())
q.pop();
cin>>n>>m;
if(n>=m)
cout<<n-m<<endl;
else
cout<<bfs(n,m)<<endl;
return 0;
}
京公网安备 11010502036488号