本文主要是介绍POJ 3278 Catch That Cow 【BFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3278
题意：假设一个人在位置x，那么他下一分钟能到达的位置是x-1,x+1,2*x，现给出你n,k，让你求从n到k最少所花费的时间
解析：直接bfs
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6+100;
int n,k;
int vis[maxn];
struct node
{int x,step;node() {}node(int _x,int _step){x = _x;step = _step;}
};
int bfs()
{queue<node> q;memset(vis,0,sizeof(vis));vis[n] = 1;q.push(node(n,0));while(!q.empty()){node now = q.front();q.pop();if(now.x==k)return now.step;if(!vis[now.x+1]){q.push(node(now.x+1,now.step+1));vis[now.x+1] = 1;}if(now.x>0 && !vis[now.x-1]){q.push(node(now.x-1,now.step+1));vis[now.x-1] = 1;}if(now.x*2<maxn && !vis[now.x*2]){q.push(node(now.x*2,now.step+1));vis[now.x*2] = 1;}}return -1;
}
int main()
{while(~scanf("%d %d",&n,&k))printf("%d\n",bfs());return 0;
}
这篇关于POJ 3278 Catch That Cow 【BFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
