POJ 3728

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <queue>
 4 #include <string.h>
 5 
 6 using namespace std;
 7 
 8 #define max 200040　　　　　　　　
 9 
10 queue<int >q;　　　　　　　　　　//定义一个队列，用来存每次所到达的位置
11 
12 int step[max];　　　　　　　　//用来存到达某个位置时，所用的步数
13 int next,head,m,n;
14 bool road[max];　　　　　　　　//但每次人走过之后，就记住这个地方已经被走过，因为之后在走这个地方的时候，步数肯定比第一次走的时候要多
15 
16 int dfs()
17 {
18     q.push(m);　　　　　　　　//首先把m也就是人的起始位置进队，然后对其的步数和位置进行标记
19     step[m]=0;
20     road[m]=true;
21     while(!q.empty())　　　　//当队列中没有元素时就结束循环
22     {
23         head=q.front();　　　　//head在这里代表着你此时此刻的位置
24         q.pop();
25         for(int i=0;i<3;i++)　　　　//因为要3种选择，所以用一个循环来进行，每走一次，如果之前没有走过，那么就进队列。如果走过，就跳过。
26         {　　　　　　　　　　　　　　　　//而当每一次做出选择之后，都会有三个选择来进行下一步，而这三个选择，步数是相同的，之前没走过的，就进队
27             if(i==0) next=head-1;　　　　
28         else if(i==1) next=head+1;
29         else next=2*head;
30         if(next>max||next<0) continue;
31         if(road[next]==false)
32         {
33             q.push(next);
34             road[next]=true;
35             step[next]=step[head]+1;
36         }
37         if(next==n) return step[next];　　　　//人到达了牛的位置，返回当前位置的步数
38         }
39     }
40     return 0;
41 }
42 int main()
43 {
44     memset(road,false,sizeof(road));　　　　//对road这个标记是否走过的数组进行初始化
45     scanf("%d%d",&m,&n);
46     if(m>=n) printf("%d",m-n);　　　　　　　　//当人在牛的右边的时候，则人只可能有一种走法，也就是向左走，那么步数也就是二者相差的距离；
47     else printf("%d",dfs());
48     return 0;
49 }