Problem 1012 - 奇妙的旅行
Time Limit
: 1000MS ?
Memory Limit
: 65536KB ?
Difficulty
:
Total Submit : 396? Accepted : 116? Special Judge : No
Total Submit : 396? Accepted : 116? Special Judge : No
Description
炸雞兒非常喜歡旅行，而且喜歡在坐標(biāo)軸上旅行，從起點(diǎn)A到終點(diǎn)B（0<=A，B<=100000）。他旅行的方法很特殊，喜歡用跳的，每次跳一個(gè)地方只有三種方法：
從點(diǎn)C跳到點(diǎn)C+1。
從點(diǎn)C跳到點(diǎn)C-1。
從點(diǎn)C跳到點(diǎn)2*C。
請(qǐng)問(wèn)他從A跳到B至少需要多少步？
Input
每組數(shù)據(jù)兩個(gè)整數(shù)A，B(0<=A，B<=100000)。
Output
每例輸出一行，表示至少需要的步數(shù)。
Sample Input
1 100000
0 100000
0 100000
Sample Output
21
22
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
;
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
