亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

奇妙的旅行[XDU1012]

系統 2042 0
Problem 1012 - 奇妙的旅行
Time Limit : 1000MS ? Memory Limit : 65536KB ? Difficulty :
Total Submit : 396? Accepted : 116? Special Judge : No
Description

  炸雞兒非常喜歡旅行,而且喜歡在坐標軸上旅行,從起點A到終點B(0<=A,B<=100000)。他旅行的方法很特殊,喜歡用跳的,每次跳一個地方只有三種方法:
從點C跳到點C+1。
從點C跳到點C-1。
從點C跳到點2*C。
請問他從A跳到B至少需要多少步?

Input
每組數據兩個整數A,B(0<=A,B<=100000)。
Output
每例輸出一行,表示至少需要的步數。
Sample Input
1 100000
0 100000
Sample Output
21
22
Hint
?
Source
Wang Miao
不知為什么,最近特喜歡做這樣的水水的bfs.
          #include<stdio.h>
          
            

#include
          
          <
          
            string
          
          .h>
          
            

#include
          
          <queue>


          
            using
          
          
            namespace
          
          
             std;


          
          
            struct
          
          
             node

{

    
          
          
            int
          
          
             val,step;

};


          
          
            int
          
          
             S,T;


          
          
            bool
          
           s[
          
            200010
          
          
            ];


          
          
            int
          
          
             bfs()

{

    memset(s,
          
          
            false
          
          ,
          
            sizeof
          
          
            (s));

    queue
          
          <node>
          
             q;

    
          
          
            while
          
           (!
          
            q.empty()) q.pop();

    node st;

    st.val
          
          =
          
            S;

    st.step
          
          =
          
            0
          
          
            ;

    q.push(st);

    s[S]
          
          =
          
            true
          
          
            ;

    
          
          
            while
          
           (!
          
            q.empty())

    {

        node st
          
          =
          
            q.front();

        q.pop();

        
          
          
            if
          
           (st.val==T) 
          
            return
          
          
             st.step;

        
          
          
            if
          
           (st.val+
          
            1
          
          <=T*
          
            2
          
          
            )

        
          
          
            if
          
           (!s[st.val+
          
            1
          
          
            ])

        {

            s[st.val
          
          +
          
            1
          
          ]=
          
            true
          
          
            ;

            node tmp
          
          =
          
            st;

            tmp.step
          
          ++
          
            ;

            tmp.val
          
          =st.val+
          
            1
          
          
            ;

            q.push(tmp);

        }

        
          
          
            if
          
           (st.val-
          
            1
          
          >
          
            0
          
          
            )

        
          
          
            if
          
           (!s[st.val-
          
            1
          
          
            ])

        {

            s[st.val
          
          -
          
            1
          
          ]=
          
            true
          
          
            ;

            node tmp
          
          =
          
            st;

            tmp.step
          
          ++
          
            ;

            tmp.val
          
          =st.val-
          
            1
          
          
            ;

            q.push(tmp);

        }

        
          
          
            if
          
           ((st.val<<
          
            1
          
          )<=T*
          
            2
          
          
            )

        
          
          
            if
          
           (!s[st.val<<
          
            1
          
          
            ])

        {

            s[st.val
          
          <<
          
            1
          
          ]=
          
            true
          
          
            ;

            node tmp
          
          =
          
            st;

            tmp.step
          
          ++
          
            ;

            tmp.val
          
          =st.val<<
          
            1
          
          
            ;

            q.push(tmp);

        }

    }

}


          
          
            int
          
          
             main()

{

    
          
          
            while
          
           (scanf(
          
            "
          
          
            %d%d
          
          
            "
          
          ,&S,&T)!=
          
            EOF)

    {

        
          
          
            if
          
           (S>
          
            T)

        {

            printf(
          
          
            "
          
          
            %d\n
          
          
            "
          
          ,S-
          
            T);

            
          
          
            continue
          
          
            ;

        }

        
          
          
            int
          
           ans=
          
            bfs();

        printf(
          
          
            "
          
          
            %d\n
          
          
            "
          
          
            ,ans);

    }

    
          
          
            return
          
          
            0
          
          
            ;

}
          
        

?

奇妙的旅行[XDU1012]


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 黑人特级粗α级毛片 | 91精品国产爱久久久久久 | 九九视频精品在线 | 97影院午夜在线观看琪琪 | 国产一二三区在线 | 成人国内精品久久久久影 | 毛片黄| 性激烈欧美三级在线播放 | 色综合久久综合欧美综合 | 欧美性色xo在线 | 五月亭亭免费高清在线 | 草草影院一级毛片a级 | 99视频精品全国免费 | 久久男人资源站 | 欧美成人丝袜视频在线观看 | 日本一级α一片免费视频 | 欧美成人午夜视频在线观看 | 日韩五月天 | 999资源站| 久草在线视频免费资源观看 | 精品精品国产自在香蕉网 | 国内精品一区二区三区最新 | 99亚洲精品高清一二区 | 国产成人久久精品推最新 | 日韩区欧美区 | 女性成人毛片a级 | 黄色在线视频观看 | 亚洲精品二区 | 91视频一区 | 亚洲一级毛片免费看 | 国产亚洲精品美女一区二区 | 爱婷婷网站在线观看 | 羞污影院| 成人亚洲在线 | 国产在线精品网址你懂的 | 精品黑人一区二区三区 | 国产一区二区免费播放 | 成人公开视频 | 综合色图 | 狠狠插狠狠干 | 综合亚洲欧美 |