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
炸鸡儿非常喜欢旅行，而且喜欢在坐标轴上旅行，从起点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
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
;
}
