奇怪的电梯(bfs)

奇怪的电梯(bfs)
思路:这道题的解法很多,深搜广搜都可以,而我用深搜来解它,首先我们可以将第一个节点压入队列中,然后我们依次搜索当前楼层可达到的楼层,并且判断是否越界,如果没有越界并且该楼层未被访问过我们就将该节点压入队列中,为什么判断是否被访问呢,因为如果当前到达楼层有正确解的话早就找到退出了,再次访问到它很明显他就是个死循环,所以我们要做一个访问的判断,并且当前楼层压入队列过后也要设置为已访问;
上代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b,lt[205];
bool vis[205]; 访问数组
struct node{int id,step;}x;
queue<node> q;
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)cin>>lt[i];
	q.push((node){a,0}); //将第一个压入队列中
	while(!q.empty()){ //如果队列不为空继续执行循环
		x=q.front();q.pop(); //将队头节点赋值给x,并且弹出队头节点;
		if(x.id==b)break; //如果当前队头节点等于我们要找的楼层,直接退出
		int xx=x.id+lt[x.id]; //将上和下回到达的赋值给xxyy方便我们敲代码(懒而已)
		int yy=x.id-lt[x.id];
		if(xx<=n&&!vis[xx])q.push((node){xx,x.step+1}),vis[xx]=1; //如果未越界并且未被访问,压入队列并且标记为已访问,步数加1;
		if(yy>=1&&!vis[yy])q.push((node){yy,x.step+1}),vis[yy]=1;
	}
	if(x.id==b)cout<<x.step;
	else cout<<-1;
	return 0;
}
上一篇:关于js异步上传文件


下一篇:【Ybtoj 第5章 例题2】山峰和山谷【广搜】