POJ 3278 -- Catch That Cow

 题意：

 

给定两个整数n和k

 

通过 n+1或n-1 或n*2 这3种操作，使得n==k

 

输出最少的操作次数

解题思路：

@使用BFS，已经访问过的数值不再进行下一层的搜索，使用bool visit[maxn]标记，k最大为10W，所以设置maxn为10W+3足矣

@进行剪枝 当前要检索的数值为n，其下一层的数值有三个取值n-1,n+1,2*n

　　设这个取值为temp

　　1.temp<0 或者 temp>maxn 越界，则不管它

　　　　简单说明一下我对最大值越界的理解吧...如果k=100000，当temp=100020>100003(maxn)应该舍弃，因为若有一个数为100002，则100002到100000的步数定比100020少。最小值越界同理。

　　2.temp已经访问过，不再进行处理

 

1）使用STL的queue

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn = 100003; 6 int change(int x,int ch) 7 {
    ///0为x-1,1为x+1,2为2*x 8     if(ch == 0) 9         return x-1;10     if(ch == 1)11         return x+1;12     if(ch == 2)13         return 2*x;14 }15 16 struct node{17 int num;18 int deep;19 node(int num,int deep):num(num),deep(deep){}20 };21 22 bool visit[maxn];23 24 int main()25 {26     int n,k;27     while(cin>>n>>k)28     {29         queue
        
          q;30         memset(visit,false,sizeof(visit));31         node u(n,0);32         q.push(u);33         visit[n] = true;34         int head = 0;35         int rear = 1;36         while(!q.empty())37         {38             u = q.front();q.pop();39             if(u.num == k)40             {41                 cout<
         
          <
         
        
       
      
     

 

2）使用数组

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn = 200030; 6 int change(int x,int ch) 7 {
    ///0为x-1,1为x+1,2为2*x 8     if(ch == 0) 9         return x-1;10     if(ch == 1)11         return x+1;12     if(ch == 2)13         return 2*x;14 }15 16 struct node{17 int num;18 int deep;19 };20 int visit[maxn];21 node queue[maxn];22 int main()23 {24     int n,k;25     while(cin>>n>>k)26     {27         memset(visit,false,sizeof(visit));28         queue[0].num = n;29         queue[0].deep = 0;30         visit[n] = true;31         int head = 0;32         int rear = 1;33         while(head
        
         =0 && temp<=maxn && !visit[temp])///进行剪枝45                 {46                     queue[rear].num = temp;47                     queue[rear++].deep = queue[head].deep+1;48                     visit[temp] = true;49                 }50             }51             head++;52         }53     }54     return 0;55 }