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 ; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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