POJ3278 Catch That Cow-数字星空

Catch That Cow

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

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

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.

题目大意：

FJ抓位置固定不动的奶牛（二者均在一条直线上），FJ和奶牛位置分别为输入的N(0 ≤ N ≤ 100,000)和K(0 ≤ N ≤ 100,000)，FJ有两种走法

*步行：FJ可以在一分钟内从任何一个点X移动到点X-1或X+1

*传送：FJ可以在一分钟内从任何一个X点移动到2*X点

输出FJ抓带到奶牛需要的最短时间，以分钟为单位

思路：

明显的BFS，几年没摸，重新回顾BFS，手写结构体构造先进先出的队列，

AC代码：

 1 #include<stdio.h>
 2 int iswalk[100050];
 3 int p;//实时移动数组下标，视作队尾添加
 4 int q;//取数，视作队头出队
 5 int N, K;
 6 struct trajectory
 7 {
 8     int step;
 9     int num;
10 };
11 struct trajectory tra[100050];
12 int main()
13 {
14     scanf("%d %d", &N, &K);
15     tra[q].num = N;
16     tra[q].step = 0;
17     iswalk[N] = 1;
18     while(q <= p)
19     {
20         if(tra[q].num == K){
21             printf("%d\n", tra[q].step);
22             break;
23         }
24         else
25         {
26             if(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             }
32             if(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             }
38             if(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             }
44 
45             q ++;
46         }
47     }
48 }

起手错误写法：

一：for的DFS（POJ3984的代码，都是BFS，于是推翻并找到奶牛这个基础题来写）

 1 #include<stdio.h>
 2 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 3 int bfs(int x, int y);
 4 int maze[5][5];
 5 int step;
 6 int evestep[25][2];//记录轨迹
 7 int OnGo[5][5];//是否走过这个点
 8 int main()
 9 //int dir[4][2] = {(-1, 0), (1, 0), (0, -1), (0, 1)};
10 {
11 //    int step;
12     for(int i = 0; i < 5; i ++)
13         for(int j = 0; j < 5; j ++)
14             scanf("%d", &maze[i][j]);
15     int x = 0, y = 0;
16     OnGo[0][0] == 1;
17 //    int bfs(x, y);
18     bfs(x, y);
19 }
20 int bfs(int x, int y)
21 {
22     for(int i = 0; i < 4; i ++)
23     {
24         x += dir[i][0];
25         y += dir[i][1];
26         if(maze[x][y] == 1 || x < 0 || y < 0 || x > 4 || y > 4)
27             continue;
28         else if(maze[x][y] == 0 && OnGo[x][y] == 0)
29         {
30             OnGo[x][y] == 1;
31             step++;
32             evestep[step][0] = x;
33             evestep[step][1] = y;
34             bfs(x, y);
35         }
36     }
37 //}
38 //推翻重写，昨天写的是DFS
39 
40 //BFS

View Code

二：推翻重写后，依旧是DFS的思路，以为BFS会携带每一层的step

 1 #include<stdio.h>
 2 int tra[100050];
 3 int iswalk[100050];
 4 int p, q;
 5 int bfs(int FJ_x, int step)
 6 {
 7     if(FJ_x == K)
 8         return step;
 9     else
10     {
11         if((FJ_x - 1) >= 0 && iswalk[FJ_x - 1] == 0){
12             iswalk[FJ_x - 1] = 1;
13             step ++;
14             bfs(FJ_x - 1, step)
15         }
16         if((FJ_x + 1) >= 0 && iswalk[FJ_x + 1] == 0){
17             iswalk[FJ_x + 1] = 1;
18             step ++;
19             bfs(FJ_x + 1, step)
20         }
21         if((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 }

View Code