30求助
查看原帖
30求助
1244320
Delayed楼主2024/8/1 10:20
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a,b,k[N],vis[N];
struct node{
	int floor;//当前楼层
	int num;//移动次数
};
void bfs(){
	memset(vis,-1,sizeof(vis));//将整栋楼标记为-1,如果为不-1就不走(最短路径)
	queue<node>q;	
	q.push((node){a,0});//起始楼层不需要移动
	while(!q.empty()){
		node now=q.front();//当前位置指针(楼层和移动次数)
		q.pop();
		if(b==now.floor){//当前楼层等于目标楼层
			cout<<now.num;
			return;
		}
		int last1=now.floor+k[now.floor];//当前楼层往上移动
		int last2=now.floor-k[now.floor];//当前楼层往下移动
		if(last1>n || last2<0 || vis[last1]==-1 || vis[last2]==-1) continue;//超出范围
		vis[last1]=0;vis[last2]=0;
		q.push((node){last1,now.num+1});
		q.push((node){last2,now.num+1});		
	}
	cout<<-1;//上一个循环直到q空了也没有找到目标楼层(b)
	return;
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>k[i];//i层楼可以移动上下k[i]层
	}
	bfs();
	return 0;
}

2024/8/1 10:20
加载中...