| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 222142 | Accepted: 67092 |
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
Output
Sample Input
5 17
Sample Output
4
Hint
*步行：FJ可以在一分钟内从任何一个点X移动到点X-1或X+1
*传送：FJ可以在一分钟内从任何一个X点移动到2*X点
输出FJ抓带到奶牛需要的最短时间，以分钟为单位
思路：
明显的BFS，几年没摸，重新回顾BFS，手写结构体构造先进先出的队列，
AC代码：
1#include<stdio.h>2intiswalk[100050];3intp;//实时移动数组下标，视作队尾添加4intq;//取数，视作队头出队5int N, K;6structtrajectory7{8intstep;9intnum;10};11struct trajectory tra[100050];12intmain()13{14scanf("%d %d", &N, &K);15 tra[q].num =N;16 tra[q].step = 0;17 iswalk[N] = 1;18while(q <=p)19{20if(tra[q].num ==K){21printf("%d\n", tra[q].step);22break;23}24else25{26if(iswalk[tra[q].num - 1] == 0 && (tra[q].num - 1>=0) && (tra[q].num - 1) <= 100000){27 iswalk[tra[q].num - 1] = 1;28 p ++;29 tra[p].num = tra[q].num - 1;30 tra[p].step = tra[q].step + 1;31}32if(iswalk[tra[q].num + 1] == 0 && (tra[q].num + 1>=0) && (tra[q].num + 1) <= 100000){33 iswalk[tra[q].num + 1] = 1;34 p ++;35 tra[p].num = tra[q].num + 1;36 tra[p].step = tra[q].step + 1;37}38if(iswalk[tra[q].num * 2] == 0 && (tra[q].num * 2) >= 0 && (tra[q].num * 2) <= 100000){39 iswalk[tra[q].num * 2] = 1;40 p ++;41 tra[p].num = tra[q].num * 2;42 tra[p].step = tra[q].step + 1;43}4445 q ++;46}47}48}
起手错误写法：
一：for的DFS（POJ3984的代码，都是BFS，于是推翻并找到奶牛这个基础题来写）
1#include<stdio.h>2intdir[4][2] = {{-1,0}, {1,0}, {0, -1}, {0,1}};3intbfs(intx,inty);4intmaze[5][5];5intstep;6intevestep[25][2];//记录轨迹7intOnGo[5][5];//是否走过这个点8intmain()9//int dir[4][2] = {(-1, 0), (1, 0), (0, -1), (0, 1)};10{11// int step;12for(int i = 0; i < 5; i ++)13for(int j = 0; j < 5; j ++)14scanf("%d", &maze[i][j]);15int x = 0, y = 0;16OnGo[0][0] == 1;17// int bfs(x, y);18 bfs(x, y);19}20intbfs(intx,inty)21{22for(int i = 0; i < 4; i ++)23{24 x += dir[i][0];25 y += dir[i][1];26if(maze[x][y] == 1 || x < 0 || y < 0 || x > 4 || y > 4)27continue;28elseif(maze[x][y] == 0 && OnGo[x][y] == 0)29{30 OnGo[x][y] == 1;31step++;32evestep[step][0] =x;33evestep[step][1] =y;34 bfs(x, y);35}36}37//}38//推翻重写，昨天写的是DFS3940//BFS
二：推翻重写后，依旧是DFS的思路，以为BFS会携带每一层的step
1#include<stdio.h>2inttra[100050];3intiswalk[100050];4int p, q;5intbfs(intFJ_x,intstep)6{7if(FJ_x ==K)8returnstep;9else10{11if((FJ_x - 1) >= 0 && iswalk[FJ_x - 1] == 0){12 iswalk[FJ_x - 1] = 1;13 step ++;14 bfs(FJ_x - 1, step)15}16if((FJ_x + 1) >= 0 && iswalk[FJ_x + 1] == 0){17 iswalk[FJ_x + 1] = 1;18 step ++;19 bfs(FJ_x + 1, step)20}21if((FJ_x * 2) >= 0 && iswalk[FJ_x * 2] == 0){22 iswalk[FJ_x * 2] = 1;23 step ++;24 bfs(FJ_x * 2, step)25}26}27}