影分身过河 WA50分求助

常规
1

题目传送门

#include<bits/stdc++.h>
using namespace std;
int n,a[2005],ans=INT_MAX,vis[2005]; 
void dfs(int now,int step){
	if(step>ans) return;
	if(now==n){
		ans=min(ans,step);
		return;
	}if(a[now]>0){
		for(int i=now;i<=now+a[now];i++){
			if(!vis[i]){
				vis[i]=1;
				dfs(i,step+1);
			}
		}
	}else{
		for(int i=1;i<=a[now]+now;i++){
			if(!vis[i]){
				vis[i]=1;
				dfs(i,step+1);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	vis[1]=1;
	dfs(1,0);
	if(ans==INT_MAX) cout<<-1;
	else cout<<ans;
	return 0;
}
2 个赞
2

要用BFS的

3 个赞
3

DFS我没试过

2 个赞
4

感谢

2 个赞