5鍏堝叆鍒?nbsp; 鎶?鍑哄垪 5 鍙互鍙樻垚 4 ,6 , 10, ,鎶婂緱鍒扮殑鏁板叆鍒?鐒跺悗鍐嶅嚭鍒楀垎鍒鐞?.濡傛灉鍓嶉潰鍑虹幇榪囧氨涓嶅叆鍒?.瀹氫箟涓涓鏁版暟緇?鐒跺悗number[y - 1] = number[y] + 1; number[y + 1] = number[y] + 1; number[y * 2] = number[y] + 1;
Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 8341 | Accepted: 2476 |
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 Code
| Problem: 3278 | User: luoguangyao | |
| Memory: 1048K | Time: 110MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <iostream> #include <queue> using namespace::std; int number[100001] = {0}; bool num[100001] = {0}; int main() { queue<int> x; int a; int b; scanf("%d%d",&a,&b); int count = 0; number[a] = 0; x.push(a); while (x.size()) { int y = x.front(); x.pop(); num[y] = 1; if (y == b) { break; } else { if (y - 1 >= 0) { if (!num[y - 1]) { x.push(y - 1); number[y - 1] = number[y] + 1; num[y - 1] = 1; } } if (y + 1 <= 100000) { if (!num[y + 1]) { x.push(y + 1); number[y + 1] = number[y] + 1; num[y + 1] = 1; } } if (y * 2 <= 100000) { if (!num[y * 2]) { x.push(y * 2); number[y * 2] = number[y] + 1; num[y * 2] = 1; } } } } cout << number[b] << endl; return 0; }
]]>
]]>