dfs80分求优化,超时两个点
查看原帖
dfs80分求优化,超时两个点
399508
kanchui666楼主2021/5/20 19:31
#include<bits/stdc++.h>
using namespace std;
int n,a,b,k[201],mmin=0x7ffffff;
bool nb[201];
void search(int l,int t){
	if(l==b){
		if(t<mmin){
			mmin=t;
			//t=0;
		}
	}else{
		if(t>=mmin){
			return;
		}
		nb[t]=1;
		if(l+k[l]<=n){
			if(!nb[l+k[l]]){
				search(l+k[l],t+1);
			}
		}
		if(l-k[l]>=1){
			if(!nb[l-k[l]]){
				search(l-k[l],t+1);
			}
		}
		nb[t]=0;
	}
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	nb[a]=1;	
	search(a,0);
	if(mmin==0x7ffffff){
		cout<<"-1";
	}else{
		cout<<mmin;
	}
	return 0;
}
2021/5/20 19:31
加载中...