P1135 奇怪的电梯

· · 题解

由于数据原因这道题所有题解都被撤下了，我来写一篇吧。

题目大意

有一种很奇怪的电梯，每一层楼都可以停，而且第 i 层楼上有一个数字 K_i。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。如果不能满足要求，相应的按钮就会失灵。问从 A 楼到 B 楼至少要按几次按钮。

算法思路

这道题可以使用深搜做，但是个人认为广搜更容易一些且不会被 hack，因此我选择用广搜。

算法讲解

首先，我们需要建立一个结构体记录每个节点的位置与答案，并定义这种结构体的队列。


struct node //每个结点的状态
{
    int x,y; //结点位置x, 结点答案y;
};
queue<node> q; //建立以每个状态为元素的队列

接下来我们就可以打出广搜基本模板：

int bfs() //返回到达终点状态的答案
{
    q.push(node{a,0}); //初始状态入队
    vis[a]=true; //表示初始结点已访问
    while(!q.empty()) //只要队列非空,就继续循环
    {
        int x=q.front().x,y =q.front().y; //取队首
        q.pop(); //队首出队
        if(x==b) return y;
        //上

   int x_new=x+k[x],y_new=y+1; //求出子结点X
   if(x_new>=1&&x_new<=n&&vis[x_new]==false)
            { //子结点合法的3个条件：结点编号1~n，结点未访问，结点无障碍
                q.push(node{x_new，y_new}); //扩展子结点入队
                vis[x_new]=true; //标记子结点已访问
            }

        //下
            x_new=x-k[x],y_new=y+1; //求出子结点
            if(x_new>=1&&x_new<=n&&vis[x_new]==false)
            { //子结点合法的3个条件：结点编号1~n，结点未访问，结点无障碍
                q.push(node{x_new,y_new}); //扩展子结点入队
                vis[x_new]=true; //标记子结点已访问
            }
    }
    return -1; //根据题意，搜不到终点返回-1
}

最后按照要求输出答案即可。

cout<<bfs()<<endl;

通过记录

亲测可以通过。

代码是多年前的，码风比较丑陋，见谅。