计蒜客–一维坐标的移动

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

计蒜客--一维坐标的移动

题目如上,该题刚开始写bfs时,在一个while循环里面进行加减乘,然后内存超限,经过无数次的修改之后终于过题了。。

程序大体思想如下:先进行起点,终点的判断。如果起点大于终点或者起点等于终点,那么直接用起点减去终点。

接下来进行两次广搜。第一次广搜用于判断加和乘,第二次广搜用于判断减和乘。

代码如下:
 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
struct Point
{
    int x,step;
    Point(int _x,int _step):
        x(_x),step(_step) {}
};
int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    queue<Point>q;
    q.push(Point(a,0));
    if(a>b)
    {
        cout<<a-b<<endl;
        return 0;
    }
    if(a==b)
    {
        cout<<0<<endl;
        return 0;
    }
    int cnt = 0;
    while(!q.empty())
    {
        int x = q.front().x;
        int step = q.front().step;
        q.pop();

        if(x == b)
        {
            cnt = step;
            break;
        }
        if(x+1 <= n && a<b)
        {
            //cout<<1<<" "<<x<<endl;
            q.push(Point(x+1,step+1));
        }
        if(x*2 <=n && a<b)
        {
            //cout<<3<<endl;
            q.push(Point(x*2,step+1));
        }
    }
    //cout<<"cnt="<<cnt<<endl;
    while(!q.empty())
        q.pop();
    q.push(Point(a,0));
    while(!q.empty())
    {
        int x = q.front().x;
        int step = q.front().step;
        q.pop();
        //cout<<step<<endl;
        if(x == b)
        {
            if(cnt > step)
            {
                cnt = step;
            }
            break;
        }
        
        if(step > cnt)
            break;
        if(x-1 >=0)
        {
            q.push(Point(x-1,step+1));
        }
        if( x*2 == b )
        {
            q.push(Point(x*2,step+1));
        }
        if( x*2+1 == b )
        {
            q.push(Point(x*2+1,step+1));
        }
    }
    cout<<cnt<<endl;
    return 0;
}

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《计蒜客–一维坐标的移动》 发布于2018-08-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录