WA #9 why? help !
查看原帖
WA #9 why? help !
127169
Baiwhiter楼主2021/5/19 17:18
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int N=210;
int mov[]={0,-1,1};//移动 
bool vis[N];
int k[N];//当前层的按钮为什么
int tot[N];//记录到达该层需要按多少次 
int n,st,ed;
void bfs(){
	queue<int> q;//q记录当前状态(楼层) 
	tot[st]=0;
	vis[st]=1;
	q.push(st);
	
	while(q.size()){
		int now=q.front();
		q.pop();
		for(int stp=1;stp<=2;stp++){
			int nxt=now+k[now]*mov[stp];//要拓展的下一个节点
			
			if(nxt<1 && nxt>n) continue;
			if(vis[nxt]) continue;
			if(nxt==ed){//第一个拓展到的一定是最优解 
				cout<<tot[now]+1<<endl;
				return;
			}else{
				vis[nxt]=1;
				tot[nxt]=tot[now]+1;
				q.push(nxt);
			}
		}
	}
	
	cout<<-1<<endl;
}
int main(){
	memset(vis,0,sizeof(vis));
	memset(tot,0,sizeof(tot));
	scanf("%d%d%d",&n,&st,&ed);
	
	for(int i=1;i<=n;i++){
		scanf("%d",&k[i]);
	}
	
	if(st==ed){
		cout<<0<<endl;
		return 0;
	}
	bfs();
	return 0;
}
2021/5/19 17:18
加载中...