首页 > 代码库 > CDZSC_2015寒假新人（4）——搜索 A
CDZSC_2015寒假新人（4）——搜索 A
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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来找最优解，注意边界问题（我错了好多次）。。。。c+1和c*2他不可能比100000大太多，不然要减很多次就不是最优解，所以c+2和c*2我都让他小于100100.
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#define Maxn 200100using namespace std;int vis[Maxn],n,k,sum;int bfs(int a,int b){ int c; memset(vis,0,sizeof(vis)); queue<int> q; q.push(a); while(!q.empty()) { c=q.front(); q.pop(); if(c==b) { break; } if(vis[c-1]==0&&c-1>=0) { vis[c-1]=vis[c]+1; q.push(c-1); } if(vis[c+1]==0&&c+1<=Maxn/2) { vis[c+1]=vis[c]+1; q.push(c+1); } if(vis[c*2]==0&&2*c<=Maxn/2) { vis[c*2]=vis[c]+1; q.push(c*2); } } return vis[b];}int main(){#ifdef CDZSC_OFFLINE freopen("in.txt","r",stdin);#endif while(scanf("%d%d",&n,&k)!=EOF) { if(n>=k) { printf("%d\n",n-k); } else { printf("%d\n",bfs(n,k)); } } return 0;}
CDZSC_2015寒假新人（4）——搜索 A
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。