來源：https://www.luogu.org/problemnew/show/P1135

題目描述
有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第i層樓(1≤i≤N)上有一個數(shù)字Ki(0≤Ki≤N)。電梯只有四個按鈕：開，關(guān)，上，下。上下的層數(shù)等于當(dāng)前樓層上的那個數(shù)字。當(dāng)然，如果不能滿足要求，相應(yīng)的按鈕就會失靈。例如：3, 3 ,1 ,2 ,5代表了Ki(K1=3,K2=3,…),從1樓開始。在1樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有?2樓。那么，從A樓到B樓至少要按幾次按鈕呢？

輸入
共二行。

第一行為3個用空格隔開的正整數(shù)，表示N,A,B(1≤N≤200, 1≤A,B≤N) ,第二行為N個用空格隔開的非負整數(shù)，表示K i。

輸出
一行，即最少按鍵次數(shù),若無法到達，則輸出?1。

樣例輸入
5 1 5
3 3 1 2 5
樣例輸出
3
解法一：BFS
AC_code:

#include <bits/stdc++.h> using namespace std; int n,a,b; int g[205]; bool vis[205]; int f[205],flag; int BFS() {queue<int>q;q.push(a);f[a] = 0;while(!q.empty()){int k = q.front();if(k == b){return f[k];}//vis[k] = true;//vis單獨放在這標記是不對的，Ac90%,應(yīng)該是入隊就標記q.pop();int x = k + g[k], y = k - g[k];if(x<=n && !vis[x]){vis[x] = true;q.push(x);f[x] = f[k]+1;}if(y>=1 && !vis[y]){vis[y] = true;q.push(y);f[y] = f[k]+1;}}return -1;} int main() {cin>>n>>a>>b;memset(f,0,sizeof(f));memset(vis,false,sizeof(vis));for(int i = 1; i <= n; i++){cin>>g[i];}int ans = BFS();cout<<ans<<endl;return 0; }

解法二：
DFS:

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; vector<int>v[205]; bool vis[205]; int n,a,b,ans = INF ; void DFS(int s,int cnt) {if(cnt >= ans)return;if(s == b){ans = cnt;return;}for(int i = 0; i < v[s].size(); i++){if(!vis[v[s][i]]){vis[v[s][i]] = true;DFS(v[s][i],cnt+1);vis[v[s][i]] = false;}} } int main() {cin>>n>>a>>b;int x;for(int i = 1; i <= n; i++){cin>>x;int y = i + x, z = i - x;if(y<=n)v[i].push_back(y);if(z>=1)v[i].push_back(z);}DFS(a,0);if(ans == INF)cout<<-1<<endl;elsecout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的P1135 奇怪的电梯（BFS/DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。