洛谷P1135 奇怪的电梯_洛谷 奇怪的电梯

题面：

解题：

确定算法:

• 模拟过程：从起点楼层a出发，向上向下可能到楼层c1、c2，

而c1、c2又可能到达另外的四个楼层d1、d2、d3、d4……

• 显然，需要操作的数据结构是树形，a就像树根，发散出很多枝条，最终查找到b楼层……

• 由于数据量较小，N≤200，为BFS、DFS算法提供了物质基础……

DFS+剪枝：

用k[ i ]记录题目给出的i楼能上下移动的层数；
deep[ i ]记录抵达i楼层的最小步数花费；

• dfs：

到达第i楼，先标记自身已被搜索过，再向上或向下k[ i ]层，同时步数+1，

• 剪枝：

1. 我们知道，如果重复到达第i楼，并且到达的步数花费≥之前最小步数花费，那么答案不可能比之前的情况更优，即可以直接剪枝。

2. 同理，如果当前步数超过当前已有答案的最小步数，也可以直接剪枝。

DFS·AC代码奉上：

#include<iostream>
#include<algorithm>
#include<cstring>
#define MAXN 1e6+5
using namespace std;
 
int n, a, b, ans = MAXN;
int k[520];//
int deep[520] = { 0 };
 
bool legal(int num)
{
    return num <= n && num >= 1; //都满足才return true
}
 
void dfs(int pos, int step)//参数1：楼层  参数2：当前步数
{
    if (step >= deep[pos])return; //上次也走到此楼，且本次花费步数更大或相等，故不可能产生更优的答案
    deep[pos] = step; //更新走到此楼需要花费的最小步数
 
    if (pos == b)//抵达！更新答案，结束当前层搜索
    {
        ans = min(ans, step);
        return;
    }
    if (ans != MAXN && step >= ans) return;//ans存在，且当前步数超过ans，故不可能产生更优答案
 
    if (legal(pos + k[pos]))//判断要去的楼层是否合法
        dfs(pos + k[pos], step + 1);
    if (legal(pos - k[pos]))
        dfs(pos - k[pos], step + 1);
}
 
int main()
{
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)cin >> k[i];
 
    memset(deep, MAXN, sizeof(deep));//初始化深度为极大
    dfs(a, 0);//从a层楼，0步开始搜索
 
    if (ans == MAXN) { cout << -1 << endl; return 0; }//未找到
    cout << ans << endl; //找到
    return 0;
}

转载题解区大佬Stephzzz的BFS代码：

#include <iostream>
#include <queue>
using namespace std;
 
/************************************************************
广度优先搜索算法的基本思想：
1、对于初始状态入队，设置初始状态为已访问
2、如果队列不为空时，出队队头元素，否则跳到第5步
3、检查出队的元素是否为最终解，如果是则跳到第5步。
4、对于出队的元素，检查所有相邻状态，如果有效并且未访问，则将
   所有有效的相邻状态进行入队，并且设置这些状态为已访问，然后
   跳到第2步重复执行
5、检查最后出队的元素是否为最终解，如果是输出结果，否则说明无解
广度优先搜索是借助于队列这种数据结构进行搜索的，队列的特点是先
进先出（FIFO），通过包含queue这个队列模板头文件，就可以利用c++
的队列模板定义自己的队列了，队列的操作非常简单，主要有以下几个：
q.push() 入队操作
q.front() 取队头元素
q.pop() 队头元素出队
q.size() 获取队列的元素个数
q.empty() 判断队列是否为空，为空返回true，不为空返回false
广度优先搜索算法的关键是要搞清楚求解过程中每一步的相邻状态有哪些，
每个状态需要记录什么信息，在搜索过程中如何标记这些状态为已访问。
在本题中，相邻状态为当前所在楼层通过按向上或向下按钮所能到达的楼
层，每个状态要记录的信息包括楼层编号和按按钮的次数。
*************************************************************/
 
//定义队列元素的类型，QElement为结构类型，使用typedef可以定义一个新的类型名称，在程序中QElement就像int、float一样，作为一个数据类型的名称使用
typedef struct {
    int floor;  //当前所处的楼层编号
    int pushcount;  //到达该楼层所经历的步数（按按钮次数）
} QElement;
 
queue<QElement> q; //定义元素类型为QElement的队列q
 
int n,a,b;
int s[1000];     //数组s记录每个楼层按按钮后能上下的楼层数
int t[1000]={0}; //数组t记录各个楼层是否已经到达过（已访问过）
 
int main()
{
    QElement e1,e2;
    int i;
    
    cin >> n >> a >> b;
    for (i=1; i<=n; i++) cin >> s[i];
    
    e1.floor=a;
    e1.pushcount=0;
    q.push(e1);  //初始状态入队：当前楼层为a，按按钮次数为0
    t[a]=1;  //记录当前楼层已访问过
    while (!q.empty())  //当队列不为空时，继续宽度优先搜索
    {
        e2=q.front();   //获取队头元素
        q.pop();  //队头元素出队（注意：c++的队列模板类中，获取队头元素并不会将该元素从队列中删除，需要使用pop函数删除该元素）
        if (e2.floor==b) break;  //检查当前状态的楼层编号是否为b，是则说明已经找到最终解，跳出循环
        i=e2.floor+s[e2.floor];  //按向上按钮后能够到达的楼层
        if (i<=n && t[i]==0)  //如果按向上按钮能到达的楼层有效并且未访问过该楼层
        {
            e1.floor=i;
            e1.pushcount=e2.pushcount+1;
            q.push(e1);
            t[i]=1;  //设该楼层为已访问过
        }
        i=e2.floor-s[e2.floor];  //按向下按钮后能够到达的楼层
        if (i>=1 && t[i]==0)  //如果按向下按钮能到达的楼层有效并且未访问过该楼层
        {
            e1.floor=i;
            e1.pushcount=e2.pushcount+1;
            q.push(e1);
            t[i]=1;  //设该楼层为已访问过
        }
    }
    
    //如果当前楼层为b，输出按按钮次数，否则无解（输出-1）
    if (e2.floor==b) cout << e2.pushcount;
    else cout << -1;
}