洛谷P1135 奇怪的电梯 广度优先搜索

Solution：

这道题可以用bfs来做。因为电梯只能向上或者向下走且只能向上或向下走k层，并且题目要求我们求出最少按几次按钮，所以用bfs就可以了。
代码如下：

//bfs
#include<iostream>
#include<queue>
#define MAX 300
using namespace std;

struct f{
  int floor;//当前的楼层编号
  int number;//到达该楼层需要的按钮次数
}top,node;

int visit[MAX];//访问数组
int k[MAX];//记录每层的k值
int n,a,b;

void bfs(int a,int b){//a为当前楼层，b为目标楼层
  queue<f> q;
  node.floor=a;
  node.number=0;
  q.push(node);//起始楼层结点入队列
  visit[node.floor]=1;
  int c;
  while(!q.empty()){
    top=q.front();
    q.pop();//取出首结点
    if(top.floor==b){//到达目标楼层，break
        break;
    }
    c=top.floor+k[top.floor];//向上走
    if(c<=n&&visit[c]==0){//没有超出边界且该结点没有被访问
        node.floor=c;
        node.number=top.number+1;
        q.push(node);
        visit[c]=1;
    }
    c=top.floor-k[top.floor];//向下走
    if(c>=1&&visit[c]==0){//没有超出边界且该结点没有被访问
        node.floor=c;
        node.number=top.number+1;
        q.push(node);
        visit[c]=1;
    }
  }
  if(top.floor==b){
    cout<<top.number;
  }else{
    cout<<-1;
  }
}

int main(){
  cin>>n>>a>>b;
  for(int i=1;i<=n;i++){
    cin>>k[i];
  }
  for(int i=0;i<MAX;i++){
    visit[i]=0;
  }
  bfs(a,b);
  return 0;
}