【搜索入门专题1】hdu2717 H Catch That Cow
Problem 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?
* 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
题意:输入起始点和终止点,输出起始点到终止点的步数,从起始点到终止点有三种走法,1:自身步数+1;2:自身步数-1;3:自身步数*2。
思路:从起始点开始,搜索三种走法能到达的点,满足条件的点加入队列,直到找到终止点,结束函数,输出步数。
易错点:判断该点是否走过之前,首先该点必须满足在数组范围内,RE+MEL 11遍 最后还是师父给指点迷津
#include<stdio.h> #include<iostream> #include<string.h> #include<queue> using namespace std; #define N 1001000 int book[N]; int startx,endx; int sumtime; struct note{ int x; int time; }; void BFS() { note head,now_head,next1,next2,next3; queue<note>Q; head.time = 0; head.x = startx; book[startx] = 1; Q.push(head); while(!Q.empty()) { now_head = Q.front() ; Q.pop() ; if(now_head.x == endx)//找到终止点,结束函数 { sumtime = now_head.time ; return; } next1.x = now_head.x + 1;//向前走一步 next2.x = now_head.x - 1;//往后退一步 next3.x = now_head.x + now_head.x;//自身两倍 //注意步数范围 //注意先后顺序,首先满足在范围内,再判断是否走过 if(next1.x < N&&next1.x>=0&&!book[next1.x]) { book[next1.x] = 1; next1.time = now_head.time + 1; Q.push(next1); } if(next2.x < N&&next2.x >= 0&&!book[next2.x]) { book[next2.x] = 1; next2.time = now_head.time + 1; Q.push(next2); } if(next3.x < N&&next3.x >= 0&&!book[next3.x]) { book[next3.x] = 1; next3.time = now_head.time + 1; Q.push(next3); } } return; } int main() { while(scanf("%d%d",&startx,&endx)!=EOF) { sumtime = 0; memset(book,0,sizeof(book)); BFS(); printf("%d ",sumtime); } return 0; }