石油大oj 1825奇怪的電梯 bfs

連結：http://exam.upc.edu.cn/problem.php?id=1825

題目描述

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

輸入

輸入共有二行，第一行為三個用空格隔開的正整數，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行為N個用空格隔開的正整數，表示Ki。

輸出

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

樣例輸入

5 1 5
3 3 1 2 5
      

樣例輸出

3
      

思路：求最短路問題，用bfs廣度優先搜尋

比賽做了很久，因為搜尋沒有學好用dfs做了。。。

bfs：寬度優先搜尋算法（又稱廣度優先搜尋）是最簡便的圖的搜尋算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優先搜尋類似的思想。其别名又叫BFS，屬于一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以找尋結果。換句話說，它并不考慮結果的可能位置，徹底地搜尋整張圖，直到找到結果為止。（來自百度百科）

代碼：（柴學長的）

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define pi acos(-1.0)
#define maxn (101000 + 50)
#define mol 1000000009
#define inf 0x3f3f3f3f
#define Lowbit(x) (x & (-x))
using namespace std;
typedef long long int LLI;


int a[maxn], n;
bool flag[maxn];

struct node {
	int x;
	int t; //t儲存移動次數
} re[maxn];


int BFS(int st, int et) {
	queue<node> Que;
	fill(flag, flag + maxn, 0);//初始化
	node temp;
	temp.x = st, temp.t = 0;
	Que.push(temp); //把起點加入隊列
	flag[st] = 1; //标記
	while (!Que.empty()) {
		node ppp = Que.front();
		Que.pop();
		if (ppp.x == et)return ppp.t;
		int x = ppp.x;
		if (x - a[x] >= 1 && !flag[x - a[x]]) {//滿足可以向下的條件
			flag[x - a[x]] = 1;
			temp.x = x - a[x];
			temp.t = ppp.t + 1;
			Que.push(temp);
		}
		if (x + a[x] <= n && !flag[x + a[x]]) {//滿足可以向下的條件
			flag[x + a[x]] = 1;
			temp.x = x + a[x];
			temp.t = ppp.t + 1;
			Que.push(temp);
		}
	}
	return -1;
}


int main() {
	int p, q;
	scanf("%d%d%d", &n, &p, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	printf("%d\n", BFS(p, q));
	return 0;
}