关于BFS的例题

题名：银老板家的电梯

题目描述

众所周知银老板是喀兰贸易的老大，银老板家也很有钱，上下楼都要用电梯，但是电梯里面没有按钮，电梯外面有上和下，按上你就会上升mi层，按下你就会下降mi层，即到达i+mi层或者i-mi层，i是你的当前楼层。现在银老板在p层，他想要去t层，请你帮帮银老板他最少需要按多少下按钮可以到达目的地。说不定他就来到你岛了呢？如果你还没有理解题意的话好吧我就举个例子：比如银老板在第2层，想要去第5层，且m依次为4,1,2,3,4;则他最少需要按2次（连续按2次上或者先按1次下再按1次上）才能到达目的地。（楼层>=1）

输入
第一行一个n,p,t（1<=n,p,t<=200）

第二行n个整数m1,m2…….mn;（0<=mi<=50）

输出
一个整数表示从p层到t层最少需要按多少次。如果不能到达输出-1。

输入样例 1
5 2 5
4 1 2 3 4

输出样例 1
2

输入样例 2
6 3 2
1 2 3 4 5 6

输出样例 2
-1

解题思路

根据题意可知，每层楼对应的下一层选项最多有两个，所以我们采用二维数组来存储每一层的一些信息。再来采用BFS算法，在使用BFS算法时我们需要一个队列，对于已经入队的楼层，我们先检查它是否是我们要达到的楼层，若不是则出列，并且将它的下一层入队，是则直接输出该楼层的循环次数。

源码

第一种思路：这是正宗的BFS算法

#include<iostream>
#include<queue>
using namespace std;
struct floor{
    int pos;
    int count;
};
const int Max= 201;
queue<floor> q;
int a[Max];
bool b[Max];
int M[2]={1,-1};
int go(int s,int e,int n){
    floor now,next,first;
    first.count=0;
    first.pos=s;
    q.push(first);
    b[s]=true;
    while(!q.empty()){
        now=q.front();
        if(now.pos==e){
            return now.count;
        }
        for(int i=0;i<2;i++){
            int tmp=now.pos+M[i]*a[now.pos];
            if(b[tmp]!=true&&tmp>0&&tmp<=n){
                next.pos=tmp;
                next.count=now.count+1;
                q.push(next);
                b[tmp]=true;
            }
        }
        q.pop();
    }
    return -1;
}
int main(){
    int n,s,e;
    cin>>n>>s>>e;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }    
    cout<<go(s,e,n);
    return 0;
}

第二种思路：用递归投机取巧

#include<iostream>
#include<algorithm>
using namespace std;
const int N=220;
int num[N];
bool re[N];
int n,b=99999,a=0,p,t;
void go(int k,int a)
{
    if(a>b) return;
    if(!re[k+num[k]]&&k+num[k]<=n) {
        re[k+num[k]]=true;
        a++;
        go(k+num[k],a);
        a--;
        re[k+num[k]]=false;
    }
    if(!re[k-num[k]]&&k-num[k]>0) {
        re[k-num[k]]=true;
        a++;
        go(k-num[k],a);
        re[k-num[k]]=false;
        a--;        
    }
    if(k==t) b=a;
}
int main()
{
    cin>>n>>p>>t;
    for(int i=1;i<=n;i++)
    cin>>num[i];
    re[p]=true;
    go(p,0);
    if(b==99999)
       cout<<-1<<endl;
      else
       cout<<b<<endl;
}

这是正解。