我的:
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int minn=2e9,n,a,b,k[205],box[205];//box表示每层楼出现的次数,为2停止,要回溯!!
void dfs(int step,int nowf)
{
if(nowf==b)
{
minn = min(minn,step-1);
return;
}
if(box[nowf]==2)return;
if(nowf+k[nowf]<=n)
{
box[nowf+k[nowf]]++;
dfs(step+1,nowf+k[nowf]);
box[nowf+k[nowf]]--;
}
if(nowf-k[nowf]>=1)
{
box[nowf-k[nowf]]++;
dfs(step+1,nowf-k[nowf]);
box[nowf-k[nowf]]--;
}
}
int main(){
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
cin>>k[i];
dfs(1,a);
if(minn == 2e9)cout<<-1;
else
cout<<minn;
return 0;
}
(80pts)
题解的:
#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,ans=0x7ffffff;
int to[205];
bool vis[205];
void dfs(int now,int sum)//now表示当前搜到的楼层,sum表示按钮次数
{
if(now==b) ans=min(ans,sum);
if(sum>ans) return;
vis[now]=1;
//不越界就搜
if(now+to[now]<=n&&!vis[now+to[now]]) dfs(now+to[now],sum+1);
if(now-to[now]>=1&&!vis[now-to[now]]) dfs(now-to[now],sum+1);
vis[now]=0;//回溯
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++) scanf("%d",&to[i]);
vis[a]=1;
dfs(a,0);
if(ans!=0x7ffffff) printf("%d",ans);
else printf("-1");
return 0;
}
(100pts unaccept) 两种都卡第一个点了