POJ 3278（BFS）

题面
Catch That Cow
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入格式：
两个整数，N和K
输出格式：
一个整数，农夫抓到牛所要花费的最小分钟数
样例.in
5 17
样例.out
4

题目分析
题目概述：我们可以将题意理解为 将整数n转化为整数k，有 *2，+1，-1 的操作，求出最少需要几步
这（可能）是一道入门的广度优先搜索题（应该是我太弱了，觉得不是，QAQ，被虐，好久才搞懂）

我们可以用队列来写，在过程可以进行判重等操作；
对于队列的做法，可以用下图来理解：

（自己手画的图，有一点丑，重复的用斜线划掉了（模拟判重的部分），需要的次数是4（有4层，根节点不算））

我们可以将三次的小操作涵盖在一次大操作里，像上面的树图一样，融合在他们的小父亲节点中（因为还有一个大的根节点）

大体的算法框架

     初始化；

    while (队列不空)
        {
            取出目前的队列首位；

            if (判断是否 == k)  
                {
                    输出;
                    跳出；
                }

            记录下当层；

            if (看是否能进行扩大的操作)
                {
                    进行*2的操作（同时要录入队列）；

                    进行+1的操作（the same as that）；
                        }
                }

            if (看是否能-1)
                {
                    进行-1的操作（the same one）
                }

            摘掉子父节点（用过的）；
        }

代码

#include <bits/stdc++.h>
using namespace std;

struct node        //node是我们声明的一个类型（在下面的队列（line）有用的）
{
    int now;         //现在的值
    int cnt;         //统计生成的三叉树的层数
}q,p;         //q是工具的作用（一个托儿），p是实际的状态

int vis[400010],n,k;       //vis存那些数用过

int main()
{

    queue<node>line;      //队列的建立（line也是结构体，有同样的属性）

    cin>>n>>k;         //输入

    memset(vis,0,sizeof(vis));       //vis初始化，所有的数都没有用过
    p.now = n;                  //将n确认为当前的值
    p.cnt = 0;                  //当前层数为0
    line.push(p);               //将p压入队列
    vis[p.now] = 1;             //这位置要打标记，防止走回来了

    while (!line.empty())
        {
            p = line.front();        //将队列（line）的属性值给p（队列line也是结构体类型，也有p的属性）

            if (p.now == k)         //边界条件
                {
                    cout<<p.cnt;         //输出p.cnt（层数，最少步数）
                    break;         //跳出循环
                }

            p.cnt++;       //无论如何层数要+1（算上小节点们的父亲）

            if (p.now < k)         //判断可否进行加的操作
                {
                    q = p;                //给工具结构体赋值
                    q.now = p.now * 2;        //进行*2的操作
                    if (vis[q.now] == 0 && q.now != 0)     //判断是否用过这个数，但也要判断一下是否为0，因为0乘任何数都是0，没意义
                        {
                            vis[q.now] = 1;        //打标记
                            line.push(q);          //压入队列
                        }

                    q = p;                //给工具结构体赋值
                    q.now = p.now+1;      //对工具结构体进行操作
                    if (vis[q.now] == 0)      //判断次数有没有用过
                        {
                            vis[q.now] = 1;       //打标记
                            line.push(q);         //压入队列
                        }
                }

            if (p.now > 0)       //判断能不能进行-1的操作（不可以有负数）
                {
                    q = p;         //给工具结构体赋值
                    q.now = p.now-1;       //对工具结构体进行操作
                    if (vis[q.now] == 0)       //判断此数是否用过
                        {
                            vis[q.now] = 1;    //打标记
                            line.push(q);      //将当前的q（q.now,q.cnt）压入队列
                        }
                }

            line.pop();       //摘掉子父节点
        }

    return 0;     //完美的结束程序
}

                                       **蒟蒻新星c_uizrp_dzjopkl原创**