【重拾计划】深搜广搜 | luogu P1135 奇怪的电梯

本文主要是介绍【重拾计划】深搜广搜 | luogu P1135 奇怪的电梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

luogu P1135 奇怪的电梯

题目描述
方法一 : 深搜dfs
方法二：广搜bfs
其他解法

题目描述

luogu P1135 奇怪的电梯

方法一 : 深搜dfs

从点A出发，找到符合条件的点一直往下搜即可

代码实现如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a,b;
int ans=0x7fffffff;
int k[210],vis[210];
int minn(int x,int y)
{return x<y?x:y;
}
void dfs(int x,int step)
{if(step>ans) return;if(x==b) ans=minn(ans,step);int u=x+k[x],d=x-k[x];if(u>=1&&u<=n&&!vis[u]){vis[u]=1;dfs(u,step+1);vis[u]=0;}if(d>=1&&d<=n&&!vis[d]){vis[d]=1;dfs(d,step+1);vis[d]=0;}return ;
}
int main()
{cin>>n>>a>>b;for(int i=1;i<=n;++i) cin>>k[i];vis[a]=1;dfs(a,0);if(ans==0x7fffffff) ans=-1;cout<<ans<<endl;return 0;}

方法二：广搜bfs

每个点扩展出最多两个点，广度优先，对于此题来说时间更优

代码实现如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a,b,ans=-1,sum;
int f[2]={1,-1};
int que[1000010][2];
bool vis[210];
int k[210];
void bfs(int x)
{int h=0,t=1;que[t][0]=x; que[t][1]=0;vis[que[t][0]]=1;while(h<t){++h;for(int i=0;i<=1;++i){int x0=que[h][0]+k[que[h][0]]*f[i];if(x0>=1&&x0<=n&&!vis[x0]){++t; que[t][1]=que[h][1]+1;vis[x0]=1;que[t][0]=x0; //printf("que[%d]=%d \n",t,que[t]);if(x0==b){h=t; sum=que[t][1]; break;}}}}
}
int main()
{cin>>n>>a>>b;for(int i=1;i<=n;++i) cin>>k[i];if(a==b) ans=0;else bfs(a);if(sum!=0) ans=sum;cout<<ans<<endl;return 0;
}