洛谷 P1135 奇怪的电梯 刷题笔记 DFS
分析题目
直接暴搜
但是我们要保证搜遍所有的路径
所以每个点都向上/向下 如果可以搜的话
用一个状态数组来存到每个位置所用的最少步数
如果当前步数超出该最少步数 也不进行搜索
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
const int INF =0x3f3f3f3f;
int ans = 220;
int a[210];
int b[210];
void dfs(int dx, int step){
b[dx] = step ;
if(dx + a[dx] <= n && step+1 < b[dx+a[dx]]){
dfs(dx+a[dx],step+1);
}
if( dx - a[dx] > 0 && step+1 < b[dx-a[dx]]){
dfs(dx-a[dx],step+1);
}
}
int main(){
cin>>n>>x>>y;
for(int i = 1;i <= n;i++){
cin>>a[i];
}
memset(b,0x7f,sizeof b);
dfs(x,0);
if(b[y]>230){
cout<<-1;
}else{
cout<<b[y];
}
return 0;
}
原文地址：https://blog.csdn.net/2301_78763076/article/details/145206242
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！