dfs求助帖 80分
查看原帖
dfs求助帖 80分
765526
zhayu__artgx楼主2023/10/20 20:23
#include<bits/stdc++.h>
using namespace std;
int n,x,y,ans=111111111;
int a[2005];
bool flag[2005];
void DFS(int xz,int yj){//深度优先搜索 
    if(xz==y){
    	ans=min(ans,yj);
	}
    if(xz>ans){//边界 
    	return;
	}else if(yj<=ans){//剪枝,yj已经比答案大就不可能是最小答案 
		///否则就搜索 
    	flag[xz]=true;
   		//分类讨论 
    	if(xz+a[xz]<=n and !flag[xz+a[xz]]){
    		DFS(xz+a[xz],yj+1);
		}
    	if(xz-a[xz]>=1 and !flag[xz-a[xz]]){
    		DFS(xz-a[xz],yj+1);
		}
    	flag[xz]=false;//归0回溯
	}
}
int main(){ 
    scanf("%d%d%d",&n,&x,&y);
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
	}
    flag[x]=true;
    DFS(x,0);
    if(ans!=111111111){//特判 
    	printf("%d",ans);
	}else{
    	printf("-1");
	}
    return 0;
}
2023/10/20 20:23
加载中...