poj 3278 Catch That Cow(经典bfs)

poj 3278 Catch That Cow(经典bfs)

题目：​​class="data-table" data-id="t7a7e9d1-ebcX21dD" data-transient-attributes="class" data-width="802px" style="width: 100%; outline: none; border-collapse: collapse;">

Default

Catch That Cow

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.

分析：将三种变化模拟成三条路，最终的结果是由A到达B的最短时间，所以联想到BFS。

虽然很多人说这是一道水题，但我却在前几次都WA了(555 T_T)  哎，走过的点就不该再走了！标记一下。

#include #include #include using namespace std;const int maxn=1e5+10;typedef long long LL;LL n,k;struct node{ LL dex,step; LL go(LL x){ if(x==1) return dex+1; else if(x==2) return dex-1; else if(x==3) return dex*2; }}p[maxn];bool vis[maxn];node que[maxn];void bfs(node start){ LL q1=0,q2=0; que[q2++]=start; vis[start.dex]++; while(q1!=q2){ node cur=que[q1]; q1=(q1+1)%(maxn-9); for(LL i=1;i<=3;i++){ LL dex=cur.go(i); if(dex>maxn-10 || dex<0 || vis[dex]>0) continue; p[dex].step=cur.step+1; que[q2]=p[dex]; q2=(q2+1)%(maxn-9); vis[dex]++; if(dex==k) return ; } }}int main(){ //freopen("cin.txt","r",stdin); while(cin>>n>>k){ if(n==k) { puts("0"); continue; } memset(vis,0,sizeof(vis)); for(LL i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。