正经题解!!!!!!!!
2026-08-20 01:27:19
发布于:江苏
1阅读
0回复
0点赞
首先看到这题时,原本思路是用深搜写,然后下面是正常深搜代码(但深搜也能做)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int x,y,n;
int a[210];
int ans=1e8;
bool flag=false;
void dfs(int val,int step){
if(val==y){
flag=true;
ans=min(ans,step);
return;
}
if(val-a[val]>=1)dfs(val-a[val],step+1);
if(val+a[val]<=n)dfs(val+a[val],step+1);
}
int main(){
scanf("%*****",&n,&x,&y);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
dfs(x,0);
if(flag)cout<<ans;
else cout<<-1;
return 0;
}
然后就会得到以下美丽的测试点

正确率只有45.5%



,个人认为是dfs直接爆掉了,因为这题数据范围给的是200,一般深搜的数据范围都在十几二十几这样子,所以报的是MLE显然这道题还是广搜好做一点
(其实深搜也能做但广搜好做更好想就用了)
以下是广搜AC代码
#include <bits/stdc++.h>
using namespace std;
struct node{
int num,step; //num是索引下标,step是操作次数
};
int n,x,y;
int a[210];
int ans=1e8;//设立初始答案为极大值
bool flag=false;//建立标记
void bfs(){
queue <node> q;
q.push(node{x,0});//将初始点下标加入队列
while(q.size()){
node t=q.front();
q.pop();
if(t.num==y){//如果遍历到了y就进行ans的答案更新
flag=true;//将标记改为true
ans=min(ans,t.step);//更新答案
return;
}
//判断点位是否合法
if(t.num-a[t.num]>=1)q.push(node{t.num-a[t.num],t.step+1});
if(t.num+a[t.num]<=n)q.push(node{t.num+a[t.num],t.step+1});
}
}
int main(){
scanf("%*****",&n,&x,&y);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
bfs();
if(flag)cout<<ans;//判断标签如果被标记就输出ans
else cout<<-1;//否则输出-1
return 0;
}
这里空空如也



有帮助,赞一个