题解：P1135 奇怪的电梯

· · 题解

题目传送门

使用博客阅读效果更佳

这是一道搜索题，本题解介绍广度优先搜索（BFS）的做法。

相较于 DFS，BFS 更适合于解决“寻找走出迷宫的路线”这一类的题目。接下来给大家介绍一下如何用 BFS 实现这个问题。

  1. 建立一个队列（不会队列的同学请出门右转至 B3616 【模板】队列）。

  2. 将迷宫的入口的节点编号入队。

  3. 取出队首。如果队首是终点，返回。否则，对上下左右四个方向扩展：如果该点没有被访问过，且该点没有越界，则将其入队。

  4. 重复执行 3. 直到队列为空。

在本题中，迷宫的入口相当于楼层 A，迷宫的出口就相当于楼层 B。每次取出队首节点 i 时，就向楼层 i+K_i 和楼层 i-K_i 扩展。

下面给出核心代码：

const int MAXN=205;
int k[MAXN];
bool book[MAXN];//book[i]=0时表示第i层还没有被访问过，
                //book[i]=1时表示第i层被访问过。
struct F {
  int lc,bs;//由于题目求的是步数，所以建立一个结构体存当前楼层和步数。
};
int bfs(int n,int a,int b) {
  queue<F>q;//建立队列（步骤1）。
  q.push((F){a,0});//将楼层A入队（步骤2）。
  while(!q.empty()) {
    //------步骤3------
    F f=q.front();//取出队首
    q.pop();
    if(f.lc==b)//是终点，返回步数。
      return f.bs;
    if(f.lc+k[f.lc]<=n&&!book[f.lc+k[f.lc]]) {//向楼层i+k[i]扩展。
      q.push((F){f.lc+k[f.lc],f.bs+1});
      book[f.lc+k[f.lc]]=true;
    }     
    if(f.lc-k[f.lc]>=1&&!book[f.lc-k[f.lc]]) {//向楼层i-k[i]扩展。
      q.push((F){f.lc-k[f.lc],f.bs+1});
      book[f.lc-k[f.lc]]=true;
    }     
  }
  return -1;//无法到达，返回-1。
}