- 影分身过河
题目ID：15694必做题100分
最新提交：
Wrong Answer
70 分
历史最高：
Wrong Answer
70 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
小兰进入森林探险后迷路了，现在有一条河挡在了他的面前，好在河上漂浮着
�
n个木桩，每个木桩都有自己的编号(
1
,
2
,
.
.
.
�
1,2,…n)以及魔法值
�
�
a
i
(可能是正数也可能是负数)，小兰是忍者高手，当他站在第
�
i个木桩上时，如果该木桩的魔法值
�
�
0
a
i
0，那么他可以使用影分身之术选择传送到第
�
�
(
1
≤
�
≤
�
�
)
i+k(1≤k≤a
i
)个木桩上，如果木桩的魔法值
�
�
<
0
a
i
<=0，那么他可以传送到
[
1
,
�
+
�
�
]
[1,i+a
i
]中的任意一个木桩上。
现在小兰在
1
1号木桩，他需要传送到编号为
�
n的木桩上才能顺利过河，每次使用影分身之术都会消耗
1
1点体力，小兰想尽可能的节省体力，他想知道最少消耗多少体力才能顺利过河，如果无论如何都无法过河，则输出
−
1
−1。
输入格式
第一行包含一个正整数
�
(
2
<
�
<
2000
)
n(2<n<2000)。
第二行包含
�
n个整数
�
1
,
�
2
,
.
.
.
,
�
�
(
1
<
∣
�
�
∣
<
2000
)
a
1
,a
2
,…,a
n
(1<∣a
i
∣<2000)，表示木桩的魔法值。
输出格式
如果能够过河，输出一个整数，表示最少消耗的体力；
否则输出
−
1
−1。
样例
Input 1
4
2 2 -1 2
Output 1
2
Input 2
2
-1 -2
Output 2
-1
样例解释
对于样例1，小兰在
1
1号木桩上可以选择传送到
2
2号木桩，再从
2
2号木桩传送到
4
4号木桩从而顺利过河。
一共传送
2
2次，消耗的体力为
2
2。
对于样例2，小兰只能一直呆在
1
1号木桩上。
#include<bits/stdc++.h>
using namespace std;
int dx[4005],vis[4005];
int n;
void bfs(int sx){
queueque;
vis[sx]=0;
que.push(sx);
while(que.size()){
int hd=que.front();
que.pop();
if(hd==n){
cout<<vis[n];
return;
}
if(dx[hd]>0){
for(int i=1;i<=dx[hd];i++){
int nx=hd+dx[i];
if(nx>n||nx<1||vis[nx]!=-1)continue;
vis[nx]=vis[hd]+1;
que.push(nx);
}
}
else{
for(int i=1;i<=hd+dx[hd];i++){
int nx=i;
if(nx>n||nx<1||vis[nx]!=-1)continue;
vis[nx]=vis[hd]+1;
que.push(nx);
}
}
}
cout<<vis[n];
}
int main(){
memset(vis,-1,sizeof(vis));
cin>>n;
for(int i=1;i<=n;i++)cin>>dx[i];
bfs(1);
return 0;
}