首页 > 代码库 > POJ - 3278

POJ - 3278

2024-07-13 08:32:05   220人阅读

Catch That Cow
Time Limit: 2000MS　　Memory Limit: 65536KB　　64bit IO Format: %I64d & %I64u

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.

Source

USACO 2007 Open Silver
双向宽搜，判重数组开到20万。
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <string> 7 #include <vector> 8 #include <queue> 9 #include <stack>10 #include <set>11 #include <map>12 #include <limits.h>13 #include <bitset>14 #define F "%I64d"15 using namespace std;16 typedef long long ll;17 int dp[2][200000],N,K;18 queue<int> QN,QK;19 int bfs()20 {21     while(!QN.empty())QN.pop();22     while(!QK.empty())QK.pop();23     memset(dp,-1,sizeof dp);24     QN.push(N);25     QK.push(K);26     dp[0][N] = dp[1][K] = 0;27     while(1)28     {29         if(QN.front() > 1 && dp[0][QN.front() - 1] == -1)30         {31             dp[0][QN.front() - 1] = dp[0][QN.front()] + 1;32             if(dp[1][QN.front() - 1] != -1)return dp[0][QN.front() - 1] + dp[1][QN.front() - 1];33             QN.push(QN.front() - 1);34         }35         if(QN.front() < 100000 && dp[0][QN.front() + 1] == -1)36         {37             dp[0][QN.front() + 1] = dp[0][QN.front()] + 1;38             if(dp[1][QN.front() + 1] != -1)return dp[0][QN.front() + 1] + dp[1][QN.front() + 1];39             QN.push(QN.front() + 1);40         }41         if(QN.front() < 100000 && dp[0][QN.front() << 1] == -1)42         {43             dp[0][QN.front() << 1] = dp[0][QN.front()] + 1;44             if(dp[1][QN.front() << 1] != -1)return dp[0][QN.front() << 1] + dp[1][QN.front() << 1];45             QN.push(QN.front() << 1);46         }47         if(QK.front() > 1 && dp[1][QK.front() - 1] == -1)48         {49             dp[1][QK.front() - 1] = dp[1][QK.front()] + 1;50             if(dp[0][QK.front() - 1] != -1)return dp[1][QK.front() - 1] + dp[0][QK.front() - 1];51             QK.push(QK.front() - 1);52         }53         if(QK.front() < 100000 && dp[1][QK.front() + 1] == -1)54         {55             dp[1][QK.front() + 1] = dp[1][QK.front()] + 1;56             if(dp[0][QK.front() + 1] != -1)return dp[1][QK.front() + 1] + dp[0][QK.front() + 1];57             QK.push(QK.front() + 1);58         }59         if((QK.front() & 1) == 0 && dp[1][QK.front() >> 1] == -1)60         {61             dp[1][QK.front() >> 1] = dp[1][QK.front()] + 1;62             if(dp[0][QK.front() >> 1] != -1)return dp[1][QK.front() >> 1] + dp[0][QK.front() >> 1];63             QK.push(QK.front() >> 1);64         }65         QN.pop();66         QK.pop();67     }68 }69 int main()70 {71 N:    while(~scanf("%d%d",&N,&K))72     {73         if(abs(N - K) <= 1){printf("%d\n",abs(N - K));continue;}74         if((N << 1) == K){puts("1");continue;}75         if(K < N){printf("%d\n",N - K);continue;}76         printf("%d\n",bfs());77     }78     return 0;79 }


联系
我们