文章
36
粉丝
505
获赞
55
访问
370.5k
很明显这题更适合用广度优先搜索,只要到达目标层数就结束程序,具体看代码注释
#include <bits/stdc++.h>
using namespace std;
int n, a, b, ans, k[202], vis[202];//k记录每层的按钮,vis记录某一层有没有来过
struct ff
{
int floor, step;//层数和对应的步数
};
int main()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
cin >> k[i];
queue <ff> f;
f.push({ a, 0 });//记录初始楼层
vis[a] = 1;
while (!f.empty())
{
if (f.front().floor == b)//到达目标层数退出
{
cout << f.front().step;
return 0;
}
int t = f.front().floor + k[f.front().floor];//上楼
if (t <= n && !vis[t])//层数不超过最大层并且这楼没有来过
{
vis[t] = 1;
f.push({ t,f.front().step + 1 });
}
t = f.front().floor - k[f.front().floor];//下楼
if (t >= 1 && !vis[t])//层数不小于1并且这楼没有来过
{
vis[t] = 1;
f.push({ t,f.front().step + 1 });
}
f.pop();
}
cout << -1;//栈为空了都没到目标层,那么就不可能到达
return 0;
}
登录后发布评论
暂无评论,来抢沙发