终于期末考试结束了,可以说,后期的速成真的很累,考的也不是很理想,下次在写一个反思贴吧,确实,,这学期让我学到了很多的东西....
Catch That Cow
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 49711 | Accepted: 15586 |
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
解题思路:
这道题其实就是一个一维的广搜问题,然后再加上一步求解最短路,记得以前在小优的博客上看到过,求最短路的搜索问题统一使用bfs较为简单,所以,这也算是一个3方向的搜索问题了,不像dfs一样,他需要回溯,他只需要状态扩展就可以了,所以,设置一个for,写出i的三种状态,然后对i的每种状态进行更新,next = head - 1; next = head + 1; next = head * 2, 对于step[MAX]的每次的更新,一定要学会...好了,没什么说了,继续开搜索专题.
代码:
# include<cstdio> # include<iostream> # include<queue> using namespace std; # define MAX 100006 queue<int>x; bool vis[MAX]; int step[MAX]; int n,m; int bfs( int n,int k ) { int head; int next; x.push(n); vis[n] = true; step[n] = 0; while ( !x.empty() ) { head = x.front(); x.pop(); for ( int i = 0;i < 3;i++ ) { if ( i == 0 ) { next = head - 1; } if ( i == 1 ) { next = head + 1; } if ( i == 2 ) { next = head * 2; } if ( next > MAX||next < 0 ) continue; if ( !vis[next] ) { x.push(next); step[next] = step[head]+1; vis[next] = true; } if ( next == k ) return step[next]; } } } int main(void) { int n,m; while ( cin>>n>>m ) { if ( n >= m ) cout<<n-m<<endl; else cout<<bfs(n,m)<<endl; } return 0; }