抓住那头牛

举报
ReCclay 发表于 2022/02/22 00:05:12 2022/02/22
【摘要】 大致题意: 在一个坐标轴上,农夫在N点,牛在K点(假设在整个过程中牛静止不动),现在农夫可以 +1, -1, *2 的步数,问抓到牛的最小步数 采用STL的queue 第一次使用。。。 #...

大致题意:

在一个坐标轴上,农夫在N点,牛在K点(假设在整个过程中牛静止不动),现在农夫可以 +1, -1, *2 的步数,问抓到牛的最小步数

采用STL的queue 第一次使用。。。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N, K;
const int MAXN=100000;
int visited[MAXN+10];

struct Step
{
    int x;
    int steps;
    Step(int xx, int s):x(xx),steps(s){}
};

queue <Step> q;

int main()
{
    cin >> N >> K;
    memset(visited, 0, sizeof(visited));
    q.push(Step(N, 0));
    visited[N] = 1;
    while( !q.empty())
    {
        Step s=q.front();
        if( s.x == K)
        {
            cout << s.steps << endl;
            return 0;
        }
        else
        {
            if( s.x-1>=0 && !visited[s.x-1])
            {
                q.push(Step(s.x-1, s.steps+1));
                visited[s.x-1] = 1;
            }
            if( s.x+1<=MAXN && !visited[s.x+1])
            {
                q.push(Step(s.x+1, s.steps+1));
                visited[s.x+1] = 1;
            }
            if( s.x*2<=MAXN && !visited[s.x*2])
            {
                q.push(Step(s.x*2, s.steps+1));
                visited[s.x*2] = 1;
            }
            q.pop();
        }
    }
    return 0;
}
  
 

文章来源: recclay.blog.csdn.net,作者:ReCclay,版权归原作者所有,如需转载,请联系作者。

原文链接:recclay.blog.csdn.net/article/details/64465753

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。