1.6.2 奇怪的电梯(BFS)
【摘要】
Description
有一天uncle-lu做了一个梦,梦见了一种很奇怪的电梯。 大楼的每一层楼都可以停电梯,而且i层楼上有一个数字。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。 当然,如果不能满足要求,相应的按钮就会失灵。例如:3,3,1,2,5代表了,从1楼开始。在1楼,按“上”可以到4楼,按“...
Description
有一天uncle-lu做了一个梦,梦见了一种很奇怪的电梯。
大楼的每一层楼都可以停电梯,而且i层楼上有一个数字。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。
当然,如果不能满足要求,相应的按钮就会失灵。例如:3,3,1,2,5代表了,从1楼开始。在1楼,按“上”可以到4楼,按“下”是不起作用的,因为没有−2楼。
那么,从A楼到B楼至少要按几次按钮呢?
Input
第一行为333个用空格隔开的正整数,表示N,A,B
第二行为N个用空格隔开的非负整数,表示Ki。
Output
一行,即最少按键次数,若无法到达,则输出−1-1−1。
Sample Input 1
5 1 5
3 3 1 2 5
Sample Output 1
3
Hint
1≤N≤200,1≤A,B≤N
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int h[210];
typedef pair<int, int> PII;
const int N = 2000000;
int n,a,b;
int d[N];
inline int bfs()
{
queue<int> q;
memset(d, -1, sizeof d);
d[a] = 0;
q.push(a);
while (q.size())
{
auto t = q.front();
//cout<<t<<endl;
q.pop();
for (int i = 0; i <= 1; i ++ )
{
int y;
if(i) y=t+h[t];
else y=t-h[t];
if (y<=0||y>b)continue;
if (d[y] == -1)
{
d[y] = d[t] + 1;
q.push(y);
}
}
}
return d[b];
}
int main()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i ++ )
scanf("%d", &h[i]);
cout << bfs() << endl;
return 0;
}
#include<cstdio>
int n,st,ed,p=0;
int step[210],lift[210];
bool pd=true;
int main()
{
scanf("%d %d %d",&n,&st,&ed);
for(int i=1;i<=n;i++)
{
step[i]=-1;
scanf("%d",&lift[i]);
}
step[st]=0;
while(step[ed]==-1 && pd)
{
pd=false;
for(int i=1;i<=n;i++)
if(step[i]==p)
{
int j=i+lift[i];
if(j<=n && step[j]==-1)
{
step[j]=p+1;
pd=true;
}
j=i-lift[i];
if(j>0 && step[j]==-1)
{
step[j]=p+1;
pd=true;
}
}
p++;
}
printf("%d",step[ed]);
return 0;
}
两种方法都可以
文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_54227557/article/details/120606159
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)