计蒜客 一维坐标的移动

时间：2022-01-01 18:26:08

 

在一个长度为 n 的坐标轴上，蒜头君想从 A 点 移动到 B 点。他的移动规则如下：

  • 向前一步，坐标增加 1。
  • 向后一步，坐标减少 1。
  • 跳跃一步，使得坐标乘 2。

蒜头君不能移动到坐标小于 0 或大于 n 的位置。蒜头想知道从 A 点移动到 B 点的最少步数是多少，你能帮他计算出来么？

输入格式

第一行输入三个整数 n，A，B，分别代表坐标轴长度，起始点坐标，终点坐标。（50000≤A,B≤n≤5000）

输出格式

输出一个整数占一行，代表蒜头要走的最少步数。

样例输入

10 2 7

样例输出

3

 

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9 7;
16 const double PI = acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxn=1e4 10;
19 using namespace std;
20 
21 int vis[5005];
22 
23 int main()
24 {
25     #ifdef DEBUG
26     freopen("sample.txt","r",stdin);
27     #endif
28     ios_base::sync_with_stdio(false);
29     cin.tie(NULL);
30     
31     int n,a,b;
32     scanf("%d %d %d",&n,&a,&b);
33     int ans=0;
34     if(a>=b)
35     ans=a-b;
36     else //BFS
37     {
38         queue<pair<int,int> > qe;
39         vis[a]=1;
40         qe.push(make_pair(a,0));
41         while(!qe.empty())
42         {
43             int now=qe.front().first;
44             int step=qe.front().second;
45             qe.pop();
46             if(now==b)//找到了
47             {
48                 ans=step;
49                 break;
50             }
51             int to;
52             to=now 1;//前进1步
53             if(to>=0&&to<=n&&!vis[to])
54             {
55                 vis[to]=1;
56                 qe.push(make_pair(to,step 1));
57             } 
58             to=now-1;//后退1步
59             if(to>=0&&to<=n&&!vis[to])
60             {
61                 vis[to]=1;
62                 qe.push(make_pair(to,step 1));
63             } 
64             to=now*2;//跳跃一步 
65             if(to>=0&&to<=n&&!vis[to])
66             {
67                 vis[to]=1;
68                 qe.push(make_pair(to,step 1));
69             } 
70                 
71         }
72     }
73     printf("%dn",ans);
74     
75     
76     return 0;
77 }
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9 7;
16 const double PI = acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxn=1e4 10;
19 using namespace std;
20 
21 int vis[5005];
22 
23 int main()
24 {
25     #ifdef DEBUG
26     freopen("sample.txt","r",stdin);
27     #endif
28     ios_base::sync_with_stdio(false);
29     cin.tie(NULL);
30     
31     int n,a,b;
32     scanf("%d %d %d",&n,&a,&b);
33     int ans=0;
34     if(a>=b)
35     ans=a-b;
36     else //BFS
37     {
38         queue<pair<int,int> > qe;
39         vis[a]=1;
40         qe.push(make_pair(a,0));
41         while(!qe.empty())
42         {
43             int now=qe.front().first;
44             int step=qe.front().second;
45             qe.pop();
46             if(now==b)//找到了
47             {
48                 ans=step;
49                 break;
50             }
51             int to;
52             to=now 1;//前进1步
53             if(to>=0&&to<=n&&!vis[to])
54             {
55                 vis[to]=1;
56                 qe.push(make_pair(to,step 1));
57             } 
58             to=now-1;//后退1步
59             if(to>=0&&to<=n&&!vis[to])
60             {
61                 vis[to]=1;
62                 qe.push(make_pair(to,step 1));
63             } 
64             to=now*2;//跳跃一步 
65             if(to>=0&&to<=n&&!vis[to])
66             {
67                 vis[to]=1;
68                 qe.push(make_pair(to,step 1));
69             } 
70                 
71         }
72     }
73     printf("%dn",ans);
74     
75     
76     return 0;
77 }

 

 

 

 

 

 

-

相关文章