2635 - 白云校区的奶牛
白云校区的食品学院最近养了只奶牛作奶品分析，最近下大雨奶牛趁机走丢了，小明被告知奶牛正在某位置上吃草，他很想尽快捉住它。假设小明刚开始在位置X (0 ≤X≤ 100,000)，假设他与奶牛在一条直线上，奶牛在位置Y (0 ≤Y≤ 100,000)。小明有两种移动的方法：走路或瞬间移动：
(1)走路，小明可以在1秒钟从位置X 走到位置X – 1和位置X + 1;
(2)瞬间转移，小明可以在1秒钟从位置X 转移到位置2X。
由于奶牛不知道小明在追它，它在整个过程一动不动在吃草，问小明最短多长时间可以捉到这只奶牛。
Input
有多行数据，每一行有两个整数X, Y
Output
每一行输出小明捉住奶牛最短时间（秒）
Examples
Input
5 17 1 2
Output
4 1
Hint
在第一组测试数据中，小明最快捉住奶牛的路径是5-10-9-18-17, 共用了4秒钟.
Solution C
#include <stdio.h> #include <string.h> #include <stdlib.h> int n,m,t1,t2,a[400010],b[400010],c[400010],pp,i; int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==m) { printf("0\n"); continue; } for(i=0;i<=200000;i++) a[i]=0; t1=0;t2=1;b[1]=n; c[1]=0;a[n]=1; while(1) { t1++; if(t1>t2)break; if((a[b[t1]-1]==0)&&(b[t1]-1>=0)) { t2++; a[b[t1]-1]=1; b[t2]=b[t1]-1; c[t2]=c[t1]+1; if(b[t2]==m) { pp=c[t2]; break; } } if((a[b[t1]+1]==0)&&(b[t1]+1<=2*m)) { t2++; a[b[t1]+1]=1; b[t2]=b[t1]+1; c[t2]=c[t1]+1; if(b[t2]==m) { pp=c[t2]; break; } } if((a[b[t1]*2]==0)&&(b[t1]*2<=2*m)) { t2++; a[b[t1]*2]=1; b[t2]=b[t1]*2; c[t2]=c[t1]+1; if(b[t2]==m) { pp=c[t2]; break; } } } printf("%d\n",pp); } }
Solution C++
//改自http://poj.org/problem?id=3278 #include<iostream> #include <queue> #include <string.h> //for memset using namespace std; int dir[3][2]={{1,1},{1,-1},{2,0}}; const int NN = 100001; int vis[NN], step[NN]; int bfs(int N, int K) { int dir[3][2] = {{1, 1}, {1, -1}, {2, 0}}; int next, i, current; queue<int> qs; qs.push(N); vis[N] = 1; step[N] = 0; while (!qs.empty()) { current = qs.front(); qs.pop(); if (current == K) return step[current]; for (i = 0; i < 3; i++) { next = dir[i][0] * current + dir[i][1]; if (next >= NN || next <0) continue; if (vis[next] != 0) continue; vis[next] = 1; step[next] = step[current] + 1; qs.push(next); } } return -1; } int main() { int N, K; while(cin>>N>>K) { memset(vis, 0, sizeof(vis)); cout<<bfs(N, K)<<endl; } return 0; }
Hint
在第一组测试数据中，小明最快捉住奶牛的路径是5-10-9-18-17, 共用了4秒钟.