openjudge 2971: Catch the Cow Problem Solving Process (with code)

This article mainly talks about the problem-solving process of openjudge 2971: Catch the Cow. Friends in need can learn about it. I hope it can be helpful to you.

Total time limit: 2000ms

Memory limit: 65536kB

Description

The farmer knows the location of a cow and wants to catch it. Both the farmer and the cow are located on the number line. The farmer starts at point N (0<=N<=100000) and the cow starts at point K (0<=K<=100000). The farmer has two ways to move:

1. Move from X to X-1 or X 1. Each move takes one minute.

2. Move from X to 2*X. Each move takes one minute.

Suppose the cow is unaware of the farmer’s actions and stands still. What is the minimum amount of time it takes for the farmer to catch the cow?

Input

two integers, N and K

Output

an integer, the minimum number of minutes it takes for the farmer to catch the cow

Sample input

5 17

Sample output

4

This question is a water question. but. It's very confusing. To sum up, BFS is

1, the array is open enough.

2, Niu and I’s direction judgment.

3, repeat the judgment of joining the team.

4, transcendent judgment.

5, good character. This is the key.

The code is as follows:

1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int x,y;
 5 struct node
 6 {
 7     int x,times;
 8 };
 9 node q[3000010];
10 int visit[1000010];
11 int heads=1,last=1;
12 int main()
13 {
14     scanf("%d%d",&x,&y);
15     if(y<x)
16     {
17     　　printf("%d",x-y);
18     　　return 0;
19     }
20     node a;
21     a.x=x;a.times=0;
22     q[heads]=a;
23     while(heads<=last)
24     {
25     　　node n=q[heads];
26     　　heads++;
27     　　if(n.x==y)
28     　　{
29         　　printf("%d",n.times);
30         　　break;
31     　　}
32     　　node n1=n;
33    　　 n1.times++;
34    　　 n1.x+=1;
35     　　if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
36     　　n1.x-=2;
37     　　if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
38     　　n1.x+=1;
39     　　n1.x*=2;
40     　　if(n1.x<=100000&&!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
41     }
42     return 0;
43 }

　　

It’s simply embarrassing.

Related tutorials: C Video tutorial

The above is the detailed content of openjudge 2971: Catch the Cow Problem Solving Process (with code). For more information, please follow other related articles on the PHP Chinese website!