天天看點

洛谷 P1135 奇怪的電梯(BFS)

來源 link.

題目描述

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

輸入格式

共二行。

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

輸出格式

一行,即最少按鍵次數,若無法到達,則輸出−1。

樣例輸入

5 1 5

3 3 1 2 5

樣例輸出

3

看到資料較小,本蒟蒻果斷用BFS解

附上AC_code和自己的思路

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int fl[500], dis[500];//fl用來存每一層樓所能上或下的層數,dis用來判斷是否已經來過這層樓和存來這層樓的最小步驟數
int n, a, b;
int bl, upl, dol;//bl是目前的樓層,upl是上升後的樓層,dol是下降後的樓層
queue<int>q;
int main()
{
 	memset(dis, -1, sizeof(dis));//初始化dis數組
 	cin >> n >> a >> b;
 	dis[a] = 0;//因為從a層樓開始,是以dis[a]為零
 	q.push(a);//a層入隊
 
 	for (int i = 1; i <= n; i++)
  		cin >> fl[i];//輸入fl
  
 	while (q.size())//BFS本體
 	{
  		bl = q.front();//隊首的樓層為目前BFS的對象
  		upl = bl + fl[bl];//上升後的樓層
  		dol = bl - fl[bl];//下降後的樓層
  
  		if (upl >= 1 && upl <= n && dis[upl] == -1)//判斷樓層是否在範圍内
  		{
   			q.push(upl);//上升後符合條件的樓層入隊
   			dis[upl] = dis[bl] + 1;//存入目前的操作步驟數
  		};
  
  		if (dol >= 1 && dol <= n && dis[dol] == -1)//下降和上升同理
  		{
   			q.push(dol);
   			dis[dol] = dis[bl] + 1;
  		};
  
  		q.pop();//将隊首對象移除
  
 	};
 	cout << dis[b] << endl;//輸出到達b樓層所需的步驟數
 
 	return 0;
}
           

看到這麼詳細的題解和分析,可以點個贊再走嘛

這對我真的很重要!!!