Catch That Cow

Time Limit:?2000MS	?	Memory Limit:?65536K
Total Submissions:?97240	?	Accepted:?30519

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point?N?(0 ≤?N?≤ 100,000) on a number line and the cow is at a point?K?(0 ≤?K?≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point?X?to the points?X?- 1 or?X?+ 1 in a single minute
* Teleporting: FJ can move from any point?X?to the point 2 ×?X?in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers:?N?and?K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes. 思路：bfs入門題，用到一些剪枝，之前沒怎么用bfs不是很熟練，看了些其他大佬的代碼，每個點(diǎn)都有三種情況，將三種情況入隊(duì)，然后標(biāo)記這個點(diǎn)已經(jīng)訪問，最后最先達(dá)到k點(diǎn)的必為最短。直接輸出就行了 實(shí)現(xiàn)代碼： //#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<stack> #include<set> #include<list> using namespace std; #define me0(x) memset(x,0,sizeof(x)) #define pb(x) push_back(x) #define ll long long const int Mod = 1e9+7; const int inf = 1e9; const int Max = 2e5+10; vector<int>vt[Max]; queue<int>q; int dx[] = {-1, 1, 0, 0}; int dy[] = { 0, 0, -1, 1}; //void exgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}} //ll inv(ll a,ll n){ll d, x, y;exgcd(a,n,d,x,y);return (x+n)%n;} ��? //int gcd(int a,int b) { return (b>0)?gcd(b,a%b):a; } ��С��? //int lcm(int a, int b) { return a*b/gcd(a, b); } ��С���� int cnt[Max]; bool vis[Max];void bfs(int l,int r) {q.push(l);vis[l] = 1;cnt[l] = 0;while(!q.empty()){int x = q.front();q.pop();if(x==r){cout<<cnt[r]<<endl;break;}if(x-1>=0&&!vis[x-1]){vis[x-1] = 1;q.push(x-1);cnt[x-1] = cnt[x] + 1;}if(x<=r&&!vis[x+1]){vis[x+1] = 1;q.push(x+1);cnt[x+1] = cnt[x] + 1;}if(x<=r&&!vis[x*2]){vis[x*2] = 1;q.push(x*2);cnt[x*2] = cnt[x] + 1;}} }int main() {int n,m;cin>>n>>m;me0(vis);bfs(n,m);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/kls123/p/7411050.html

總結(jié)

以上是生活随笔為你收集整理的poj3278 【BFS】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。