问题P1135奇怪的电梯

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$1 \le i \le N$）上有一个数字 $K_i$（$0 \le K_i \le N$）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3, 1, 2, 5$ 代表了 $K_i$（$K_1=3$，$K_2=3$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

解答

*首先，这道题目有两种解法：深搜和宽搜*

DFS

先来说深搜，也就是暴力做法。
那咱们就往答案层搜索，首先得定义一个数组来存每一层上面的数字是多少，然后写一个dfs(int u)函数，u指当前的楼层，因为直接搜，可能会有路径是 1楼…3楼…4楼…3楼…5楼 的情况，那么三楼就被搜了两遍，这就没有必要去增加运行时间了，对比优化后的1楼…3楼…5楼，这个时间用的更少。

那么，这个代码剪枝要怎么去实现呢？我们用一个状态数组st来存储每一个楼层被走过没有,如果这个楼层被走过也就是被标记过了就不进行下一层函数，然后用一个cnt变量来记数，具体代码实现如下：

#include<iostream>
using namespace std;
const int N = 100010;

bool st[N];                    //每一层的状态数组
int _num[N],n,A,B,big = 10000;// 分别是楼层上的数字，总楼层数，当前楼层，目标楼层


void dfs(int u,int cnt)    //分别代表当前楼层，当前楼层要按的按钮数
{
    if (cnt >= big) return;     //也是一个剪枝，如果cnt大于按的最小次数就没必要进行到下一层了
    if (u == B)             // 当当前楼层是目标楼层时，记录按的次数
    {
        big = min(big, cnt);
        return;
    }

    if (u - _num[u] >= 1 && st[u - _num[u]] == false) // 判断往下走的步骤是否会越界和下一个楼层有没有走过
    {
        st[u - _num[u]] = true;//标记
        dfs(u - _num[u],cnt + 1);
        st[u - _num[u]] = false;//回溯，恢复现场
    }

    if (u + _num[u] <= n && st[u + _num[u]] == false)//跟上面那个同理，只是电梯运动方向相反
    {
        st[u + _num[u]] = true;
        dfs(u + _num[u],cnt + 1);
        st[u + _num[u]] = false;
    }
}

int main()
{
    cin >> n >> A >> B;

    for (int i = 1; i <= n; i++) scanf("%d", &_num[i]);

    dfs(A,0);
    if(big == 10000)cout<<-1<<endl; // 代表到不了目标楼层
    else cout << big;


    return 0;
}

暴力搜索还是会MLE，只有部分测试点过了，但是开始那几个测试点就是用来卡暴力解法的，那么我们就走另外一条路 BFS

BFS

宽搜不同于深搜，一般用来解最短路问题，并且还得用上队列。

在这道题目里面，队列是用于存储能进行下一步操作的位置也就是楼层。
然后，我们要用到两个数组，数组elvator来记录电梯每层显示的数字，num来存当前楼层是按几次按钮来到的。

首先我们对当前的楼层进行操作，如果往下或者往上不会越界并且往下或者往上到达的楼层的num没有记录，也就是没有到达过，那么我们把往下或者往上到达的楼层加入队列中，然后弹出队列头部也就是当前操作的楼层进行下一步操作，最后循环这个过程知道队列里面没有元素为止，以下为实现代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;


const int N = 100010;

int elvator[300],num[300];     //楼层上面的数字，到达楼层需要按的按钮次数
int n, A, B,cnt = 0;    //分别是总楼层数，当前楼层，目标楼层
queue <int> q;      //记录需要操作的楼层


int bfs()
{
    memset(num, -1, sizeof num);    //初始化记录按钮的数组
    q.push(A);           //先把最开始的楼层放进去
    num[A] = 0;           //初始化，避免又到达一次初始楼层
    while (q.size())     //循环操作直到队列里面没有需要操作的楼层为止
    {
        int up = q.front() + elvator[q.front()], down = q.front() - elvator[q.front()];//up代表假如向上走后的楼层数，down表示向下走
        if (up <= n && num[up] == -1)
        {
            num[up] = num[q.front()] + 1; //标记下一个楼层需要按的按钮数，就是当前层按钮数加一
            q.push(up); // 将下一层假如判断队列
        }
        if (down > 0 && num[down] == -1)与上面同理，就是电梯运动方向是向下
        {
            num[down] = num[q.front()] + 1;
            q.push(down);
        }
        q.pop();    //弹出当前已经操作过的楼层

    }

    return num[B];   //返回目标层的按钮数

}


int main()
{
    cin >> n >> A >> B;

    for (int i = 1; i <= n; i++) scanf("%d", &elvator[i]);


    cout << bfs() << endl;   //输出

    return 0;
}

这样一来就能AC了！