文章

36

粉丝

505

获赞

55

访问

372.6k

头像
题解:奇怪的电梯
P1072
发布于2020年3月22日 20:06
阅读数 10.2k

很明显这题更适合用广度优先搜索,只要到达目标层数就结束程序,具体看代码注释

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发