欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3278(BFS)

程序员文章站 2022-03-25 17:03:32
...

题面
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,被虐,好久才搞懂)

我们可以用队列来写,在过程可以进行判重等操作
对于队列的做法,可以用下图来理解:
POJ 3278(BFS)
(自己手画的图,有一点丑,重复的用斜线划掉了(模拟判重的部分),需要的次数是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原创**
相关标签: BFS