目錄

1.前言

2.題目：奇怪的電梯

1.題目描述

2.輸入格式

3.輸出格式

4.輸入輸出樣例

5.說明

6.題解

?3.小結(jié)

---

1.前言

哈嘍大家好啊，前一段時(shí)間小編去備戰(zhàn)藍(lán)橋杯所以博客的更新就暫停了幾天，今天繼續(xù)為大家?guī)眍}解分享，希望大家多多支持我哦~

2.題目：奇怪的電梯

1.題目描述

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

2.輸入格式

共二行。

第一行為三個(gè)用空格隔開的正整數(shù)，表示?N,A,B（1≤N≤200，1≤A,B≤N）。

第二行為?N?個(gè)用空格隔開的非負(fù)整數(shù)，表示?Ki?。

3.輸出格式

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

4.輸入輸出樣例

5.說明

對于?100%?的數(shù)據(jù)，1≤N≤200，1≤A,B≤N，0≤Ki?≤N。

本題共?16個(gè)測試點(diǎn)，前?15?個(gè)每個(gè)測試點(diǎn)?6?分，最后一個(gè)測試點(diǎn)?10?分。

6.題解

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=230;int n=0,a=0,b=0;//分別記錄大樓總高度，當(dāng)前樓層，目標(biāo)樓層
int fl[N];//記錄按鈕
int ans=1e9;//記錄次數(shù)
bool st[N];//判斷該樓層是否已經(jīng)登過void dfs(int x,int ans1){if(ans1>=ans)return ;if(x<0||x>n)return ;//超出范圍了剪枝if(x==b){ans=min(ans,ans1);return ;}if(x+fl[x]<=n&&!st[x+fl[x]]){st[x+fl[x]]=true;dfs(x+fl[x],ans1+1);st[x+fl[x]]=false;//回溯原來狀態(tài)}if(x+fl[x]>0&&!st[x+fl[x]]){st[x+fl[x]]=true;dfs(x-fl[x],ans1+1);st[x+fl[x]]=false;}
}int main(){cin>>n>>a>>b;for(int i=1;i<=n;i++){cin>>fl[i];}dfs(a,0);if(ans==1e9){printf("-1");return 0;}cout<<ans;return 0; 
}

這道題思路如下：

• ?這道題我是用dfs解決的。
• 搜索有倆條路徑：一個(gè)是向上查詢，另一個(gè)是向下查詢。
• 剪枝條件有倆個(gè)：1.如果上升或下降小于等于0或者大于n。? ? ?2.枚舉次數(shù)過大 。
• 另外為了節(jié)省時(shí)間，選擇用bool數(shù)組記錄樓層選擇狀態(tài)，以免造成某一層樓反復(fù)到達(dá)所造成的tle。

?3.小結(jié)

今天的分享到這里就結(jié)束了，希望大家多多點(diǎn)贊，多多收藏，多多支持我哦~