POJ3278 Catch That Cow

*Walking: FJ can move from any point X to point X-1 or X+1 in one minute.

* Teleportation: FJ can move from any X point to 2*X points within a minute

Output the minimum time, in minutes, needed for the FJ to catch and bring to the cow

Thoughts:

Obvious BFS, haven't touched it in a few years, revisiting BFS, handwriting structs to construct FIFO queues, the

AC Code:

 1 #include<>
 2 int iswalk[100050];
 3 int p;//Move array subscripts in real time, treated as end-of-queue additions
 4 int q;//Take the count and treat it as if the team leader is out of the team
 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 }

Starting error writing:

I: DFS for for (POJ3984's code, all BFS, so overthrow and find cows for this basic question to write)

 1 #include<>
 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];//track
 7 int OnGo[5][5];//Did you walk past this point?
 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 //Reversed and rewritten. Yesterday I wrote DFS.
39 
40 //BFS

View Code

Two: After the overthrow and rewrite, it's still the same idea of DFS, thinking that BFS will carry each layer of step

 1 #include<>
 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