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不是很熟練，看了些其他大佬的代碼，每個點都有三種情況，將三種情況入隊，然后標記這個點已經訪問，最后最先達到k點的必為最短。直接輸出就行了
實現代碼：
//#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; }
?
