Catch The Cow 抓住牛 POJ 3278 宽度优先算法

原题 

      Catch The Cow

题意 

    从初始位置，可以向 前走一步，向后走一步，向前跳2倍的距离，问最少几步走到最终位置。

Input

　　输入包含多组数据。每组数据占一行，包含两个整数a和b，表示起始坐标和目的地坐标。（0 ≤a,b≤100000）

Output

　　对于每组输入，输出一个整数，到达目的地的最少步数。

Sample Input

5      17

Sample Output

4

解题思路：

    利用宽度优先算法，求解最短步数。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a,b;
queue<int> q;
//
利用队列的先进先出
const int maxn = 100001;
int v[maxn];
// 判断 走没走过
int step[maxn];
// 用于记录步数
int bfs(int a,int b){
int head,next;
q.push(a);
// 将初始位置 push 进队列
step[a] = 0;
// 初始位置 步数为 0
v[a] = 1;
// 走过的地方为 1
while(!q.empty()){
// 当栈不为空
head = q.front();
//
head 为队列头
q.pop();
// 出队
for(int i = 0;i < 3;i++){
// 3 个方向
if(i == 0){
next = head - 1;
}
else if(i == 1){
next = head + 1;
}
else {
next = head * 2;
}
if(next < 0 || next >= maxn){
// 超出界限，不往下判断
continue;
}
if(!v[next]){
// 这里可能push 进 3 个数
q.push(next);
// push进队列
step[next] = step[head] + 1;
// 步数加一
v[next] = 1;
// 标记为走过
}
if(next == b){
return step[b];
// 走到终点，返回步数
}
}
}
}
int main(){
while(scanf("%d%d",&a,&b) != EOF){
memset(v,0,sizeof(v));
memset(step,0,sizeof(step));
// 每次初始化为0
while(!q.empty()){
q.pop();
}
if(a >= b){
printf("%dn",a-b);
// 当初始位置大于最终位置时，只能一步一步往后退
}
else{
printf("%dn",bfs(a,b));
// 宽度优先算法
}
}
return 0;
}

最后

以上就是羞涩麦片为你收集整理的Catch The Cow 抓住牛 POJ 3278 宽度优先算法的全部内容，希望文章能够帮你解决Catch The Cow 抓住牛 POJ 3278 宽度优先算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。