P1135 奇怪的电梯

admin

https://www.luogu.org/problemnew/show/P1135


题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？

输入输出格式
输入格式：
输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的非负整数，表示Ki。

输出格式：
输出文件仅一行，即最少按键次数,若无法到达，则输出-1。

输入输出样例
输入样例#1：
5 1 5
3 3 1 2 5
输出样例#1：
3

lyc

数据小……dfs剪点枝就过了

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. #include<algorithm>
   
5. const int N = 220;
   
6. const int oo = 0x3f3f3f3f;
   
7. using namespace std;
   
8. int c[N];//楼层上的数字
   
9. int st, ed, n;
   
10. int vis[N];
    
11. int ans = oo;
    
12. void dfs(int now, int sum)
    
13. {
    
14.     if(sum > ans) return ;
    
15.     if(now == ed)
    
16.     {
    
17.         ans = min(ans, sum);
    
18.         return;
    
19.     }
    
20.     if(now + c[now] <= n && vis[now+c[now]] == 0)
    
21.     {
    
22.         vis[now+c[now]] = 1;
    
23.         dfs(now+c[now], sum + 1);
    
24.         vis[now+c[now]] = 0;
    
25.     }
    
26.     if(now - c[now] >= 1 && vis[now-c[now]] == 0)
    
27.     {
    
28.         vis[now-c[now]] = 1;
    
29.         dfs(now-c[now], sum + 1);
    
30.         vis[now-c[now]] = 0;
    
31.     }
    
32. }
    
33. int main()
    
34. {
    
35.     cin>>n>>st>>ed;
    
36.     for(int i=1; i<=n; i++)
    
37.     {
    
38.         cin>>c[i];
    
39.     }
    
40.     dfs(st, 0);
    
41.     if(ans == oo)
    
42.         cout<<-1;
    
43.     else
    
44.         cout<<ans;
    
45.     return 0;
    
46. }
    

复制代码

胡雨菲菲

1. #include <cstdio>
   
2. #include <queue>
   
3. const int N = 210;
   
4. 
   
5. int n, b, a, k[N];
   
6. bool vis[N];
   
7. 
   
8. struct Sta {
   
9.     int floor, step;
   
10.     Sta(int f, int s) {
    
11.         this->floor = f;
    
12.         this->step = s;
    
13.     }
    
14. };
    
15. 
    
16. 
    
17. void BFS() {
    
18.     std::queue<Sta> Q;
    
19.     Q.push(Sta(a, 0));
    
20.     vis[a] = 1;
    
21.     while(!Q.empty()) {
    
22.         Sta s = Q.front();
    
23.         Q.pop();
    
24.         if(s.floor == b) {
    
25.             printf("%d", s.step);
    
26.             return;
    
27.         }
    
28.         int p = s.floor + k[s.floor];
    
29.         if(p > 0 && p <= n && !vis[p]) {
    
30.             vis[p] = 1;
    
31.             Q.push(Sta(p, s.step + 1));
    
32.         }
    
33.         p = s.floor - k[s.floor];
    
34.         if(p > 0 && p <= n && !vis[p]) {
    
35.             vis[p] = 1;
    
36.             Q.push(Sta(p, s.step + 1));
    
37.         }
    
38.     }
    
39.     printf("-1");
    
40.     return;
    
41. }
    
42. 
    
43. int main() {
    
44.     scanf("%d%d%d", &n, &a, &b);
    
45. 
    
46.     for(int i = 1; i <= n; i++) {
    
47.         scanf("%d", &k[i]);
    
48.     }
    
49. 
    
50.     BFS();
    
51. 
    
52.     return 0;
    
53. }
    

复制代码

张笑宇

dfs

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b,s[210],i;
   
4. int ans=999999;
   
5. bool bb[210];
   
6. void dfs(int x,int sum)///x当前楼层 sum当前次数
   
7. {
   
8.         if (x==b)
   
9.         {
   
10.                 ans=min(ans,sum);
    
11.                 return;
    
12.         }
    
13.         else if (sum<=ans)
    
14.         {
    
15.                 bb[x]=true;
    
16.                 if (x+s[x]<=n && bb[x+s[x]]==0) dfs(x+s[x],sum+1);
    
17.                 if (x-s[x]>=1 && bb[x-s[x]]==0) dfs(x-s[x],sum+1);
    
18.                 bb[x]=false;
    
19.         }
    
20. }
    
21. int main()
    
22. {
    
23.         cin>>n>>a>>b;
    
24.         for (i=1;i<=n;i++) cin>>s[i],bb[i]=0;
    
25.         dfs(a,0);
    
26.         if (ans==999999)
    
27.         {
    
28.                 cout<<"-1";
    
29.                 return 0;
    
30.         }
    
31.         cout<<ans;
    
32.         return 0;
    
33. }
    

复制代码

张笑宇

bfs

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b;///总楼层 起点 终点
   
4. const int mx=210;
   
5. int k[mx],d[mx],f[mx],s[mx];
   
6. int x[3]={0,1,-1},i;///f1向上 f2向下
   
7. int main()
   
8. {
   
9.     cin>>n>>a>>b;
   
10.     for (i=1;i<=n;i++) cin>>k[i];
    
11.     if (a==b) {cout<<"0";return 0;}
    
12.     int tail=1,head=1;
    
13.     d[1]=a,s[a]=0,f[a]=0;
    
14.     while (head<=tail)
    
15.     {
    
16.         int temp=d[head];
    
17.         for (i=1;i<=2;i++)
    
18.         {
    
19.             int q=temp+x[i]*k[temp];
    
20.             if (1<=q&&q<=n&&!s[q])
    
21.             {
    
22.                 tail++;
    
23.                 d[tail]=q;
    
24.                 s[q]=s[temp]+1;
    
25.             }
    
26.         }
    
27.         head++;
    
28.     }
    
29.     if (s[b]>0) cout<<s[b];
    
30.     else cout<<"-1";
    
31.     return 0;
    
32. }
    

复制代码

admin

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. const int mn=220;
   
5. int n,a,b,u[mn]; ///同题目的意思 U表示上下几层楼
   
6. int s[mn],f[mn],d[mn];
   
7. ///s表示现在是第几步
   
8. ///f表示爸爸是谁，从哪里来的
   
9. ///d表示进队列的先后顺序
   
10. 
    
11. int head,tail,temp,t,i;
    
12. bool bb;
    
13. int main()
    
14. {
    
15.     cin>>n>>a>>b;
    
16.     if (a==b) cout<<0;  ///特殊判断
    
17.     else
    
18.     {
    
19.         for (i=1; i<=n; i++)
    
20.         {
    
21.             cin>>u[i];
    
22.             s[i]=0;
    
23.             f[i]=0;
    
24.         }
    
25.         head=tail=1;
    
26.         d[1]=a;
    
27.         s[a]=0;
    
28.         f[a]=0;
    
29.         bb=0;
    
30.         while (tail>=head  &&  tail<=mm-1000 && !bb)
    
31.         {
    
32.             temp=d[head];
    
33.             t=temp+u[temp];
    
34.             if (t<=n && t>=1 && s[t]==0)   ///不超过范围并且曾经没有到过
    
35.             {
    
36.                 tail++;
    
37.                 d[tail]=t;
    
38.                 s[t]=s[temp]+1;
    
39.                 f[t]=temp;
    
40. 
    
41.             }
    
42.             if (t==b) bb=0;
    
43.             t=temp-u[temp];
    
44.             if (t<=n && t>=1&& s[t]==0)
    
45.             {
    
46.                 tail++;
    
47.                 d[tail]=t;
    
48.                 s[t]=s[temp]+1;
    
49.                 f[t]=temp;
    
50.             }
    
51.             if (t==b) bb=0;
    
52.             head++;
    
53. 
    
54.             /*cout<<"d ";
    
55.             for (i=1; i<=n; i++) cout<<setw(3)<<d[i];
    
56.             cout<<endl;
    
57.             cout<<"s ";
    
58.             for (i=1; i<=n; i++) cout<<setw(3)<<s[i];
    
59.             cout<<endl;
    
60.             cout<<"f ";
    
61.             for (i=1; i<=n; i++) cout<<setw(3)<<f[i];
    
62.             cout<<endl;
    
63.             */
    
64.         }
    
65.         if (s[b]==0) cout<<-1;
    
66.         else cout<<s[b];
    
67.     }
    
68.     return 0;
    
69. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b;
   
4. int f[201],now[201],s[201],h,t;
   
5. int main()
   
6. {
   
7.     cin>>n>>a>>b;
   
8.     if(a==b)cout<<0;
   
9.     else
   
10.     {
    
11.         for(int i=1; i<=n; i++)cin>>f[i];
    
12.         h=t=1;
    
13.         now[h]=a;
    
14.         s[a]=0;
    
15.         while(h<=t)
    
16.         {
    
17.             int p=now[h]+f[now[h]],
    
18.                 q=now[h]-f[now[h]];
    
19.             if(p<=n&&!s[p])
    
20.             {
    
21.                 t++;
    
22.                 now[t]=p;
    
23.                 s[p]=s[now[h]]+1;
    
24.             }
    
25.             if(q>0&&!s[q])
    
26.             {
    
27.                 t++;
    
28.                 now[t]=q;
    
29.                 s[q]=s[now[h]]+1;
    
30.             }
    
31.             h++;
    
32.         }
    
33.         if(s[b]>0)cout<<s[b];
    
34.         else cout<<-1;
    
35.     }
    
36.     return 0;
    
37. }
    

复制代码

admin

裸的BFS 当然也可以dijistra 其实所有的边长为1的时候 Dijistra不就是BFS吗？