不说废话了,上代码。我怎么都想不明白这东西会mle.....
#include <bits/stdc++.h>
using namespace std;
int n,start1,end1,now1,step;
int a[2010],no[2010],c[2010];
bool flag = false;
queue<int>b;
void bfs(){
if(b.size()>0){
now1 = b.front();
c[now1]++;
b.pop();
if (now1-a[now1] > 0&&c[now1-a[now1]] == 0){
b.push(now1 - a[now1]);
if(no[now1-a[now1]] > no[now1] + 1)
no[now1-a[now1]] = no[now1] + 1;
}
if (now1+a[now1] <= n&&c[now1+a[now1]] == 0){
b.push(now1 + a[now1]);
if(no[now1+a[now1]] > no[now1] + 1)
no[now1+a[now1]] = no[now1] + 1;
}
if(now1 == end1){
printf("%d",no[end1]);
flag = true;
return;
}
bfs();
return;
}
}
int main(){
scanf("%d%d%d",&n,&start1,&end1);
int i;
for(i = 1;i <=n;i++)
scanf("%d",&a[i]);
for(i = 1;i <=n;i++)
no[i] = 99999;
no[start1] = 0;
b.push(start1);
if(start1 == end1||n ==0){
printf("0");
return 0;
}
if(start1 >= 1&&start1<=n&&end1>=1&&end1<=n)
bfs();
else{
printf("-1");
return 0;
}
if(flag == false)
printf("-1");
return 0;
}