首页 > 代码库 > POJ 3278 Catch That Cow
POJ 3278 Catch That Cow
Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 48127 | Accepted: 15077 |
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
算法分析：bfs的一道搜索题目，一开始我以为应该是去找到某种 统一的算法公式来计算从 “起点数字” 到“终点数字”的最小步骤数，
可是想了半天都没有思路，最后想到了暴力解决问题。
可这不是bfs的算法题吗？
不错，并非是普通的线性暴力搜索，需要用到bfs的思想。仔细分析便可知道，计算机程序做不到动态的决定从当前的这一
步该怎样继续走下去 所达到的结果最优！（只限在本题）
所以我们的思路就是：从“当前节点”出发，可以到到其余3个节点，这三个节点又可以分别到达3个节点，加起来就是9个点了，
当然这9个点可能会出现重复的点，也就是说，如果该点已经被访问过了，也就没有再访问的必要了。所以要用到标记术数组。
如此继续下去，判断每一个可到达的点是不是终点即可，如果该点是 终点，返回 到达“当前节点”的步数统计数（用数组来记录）。
#include <iostream>#include <stdio.h>#include <string.h>#include <queue>#include <algorithm>using namespace std;int vis[101000], dis[101000];int bfs(int n, int k){ queue<int>q; //简历队列 q.push(n); //将起点入队列 vis[n]=1; //标记起点被访问 dis[n]=0; //此时起点到自身的步数为0 int curpos; //当前节点 while(!q.empty() ) //判断队列不为空 { curpos=q.front(); //取出当前队首元素 q.pop(); if(curpos == k) //如果等于终点 { return dis[curpos]; //返回步数 } else { if(curpos-1>=0 && curpos<=100000 && vis[curpos-1]==0 ) //判断此点是否可行 { q.push(curpos-1); //如果行，进入队列 待命 vis[curpos-1]=1; //标记该点被访问,以后不要被重复访问了 dis[curpos-1]=dis[curpos]+1; // 到达此点的步数 == 当前点的步数+1 } if(curpos+1>=0 && curpos+1<=100000 && vis[curpos+1]==0 ) //类推 { q.push(curpos+1); vis[curpos+1]=1; dis[curpos+1]=dis[curpos]+1; } if(curpos*2>=0 && curpos*2<=100000 && vis[curpos*2]==0 ) //类推 { q.push(curpos*2); vis[curpos*2]=1; dis[curpos*2]=dis[curpos]+1; } } } return 0;}int main(){ int n, k; while(scanf("%d %d", &n, &k)!=EOF) { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); printf("%d\n", bfs(n, k)); } return 0;}
POJ 3278 Catch That Cow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。