2021-03-08
思路：dfs
没有越界就继续搜下去
#include<bits/stdc++.h>
using namespace std;
int n,a,b,ans=1e9;
int t[205],v[205];//t[i]表示在i层时可以上下的层数 v[i]存储在当前走法下i层是否经过 0--未走过 1--已走过
void dfs(int floor,int k) {
if(floor==b)
ans=min(k,ans);//如果到达B层，选取最小值
if(k>ans)
return ; //如果当前K大于ans,就不用考虑了这个走法了
//向上
if(floor+t[floor]<=n&&!v[floor+t[floor]]) { //考虑是否越界或floor+t[floor这个层数已走过
v[floor]=1; //标记floor层已走过 如果未标记，可能会重复来到这层，陷入死循环
dfs(floor+t[floor],k+1);
}
//向下
if(floor-t[floor]>=0&&!v[floor-t[floor]]) {
v[floor]=1;
dfs(floor-t[floor],k+1);
}
v[floor]=0;//回溯
}
int main() {
scanf("%d%d%d",&n,&a,&b);
for(int i=1; i<=n; i++)
scanf("%d",&t[i]);
v[a]=1;//把当前A层标记为已走过
dfs(a,0);
if(ans!=1e9)
printf("%d\n",ans); //如果ans值不变，说明从A层无法到B层
else
printf("-1\n");
return 0;
}
完结撒花