洛谷: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$ 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 $N,A,B$（$1\le N\le 200$，$1\le A,B\le N$）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le N\le 200$，$1\le A,B\le N$，$0\le K_i\le N$。

思路简介 : bfs 或 floyd (由于数据更新,dfs 第一个数据TLE, 但下方也附上思路和代码)

注意!!! : 下方附有算法超链接,建议了解算法之后再看代码

• bfs 点击查看算法

BFS 广度优先搜索
bfs也就是将队首取出，并拓展子节点（即可行方案），再将队首扔掉，当队列为空的时候，就证明我们还没有找到目标节点，也就是问题无解。

具体见代码注释

#include <iostream>
#include <queue>
using namespace std;

struct node
{
    int floor, step;  // floor为当前楼层，step为到floor楼层的最小步数
};
const int N = 205;
int n, a, b;  // n组电梯按钮数  a开始  b目标
int k[N];  // 按钮
bool vis[N];  // 记录是否来过, 用来判重

void bfs(){
    if(a == b) {cout << 0; return ;}  // 特判
    vis[a] = true;  // 把初始位置标记问访问过
    queue <node> q;  // 建立队列
    q.push((node){a, 0});  // 把起始点加入队列
    while (!q.empty()) {  // 当队列不为空
        node now = q.front();  // 临时储存队首的值
        q.pop();  // 取出队首
        int floor = now.floor, step = now.step;  // 用变量保存目前的楼层和步数

        if(floor == b) {  // 如果到目标节点, 输出步数并结束
            cout << step;
            return ;
        }

        for (int i = -1; i <= 1; i += 2) {  // 计算出上楼和下楼的值, i == -1时是下楼, i == 1 时上楼 
            int new_floor = floor + i * k[floor];
            if (new_floor >= 1 && new_floor <= n && !vis[new_floor]) {  // 子节点合法 (判断楼层是否在大楼里,且未访问)
                vis[new_floor] = true;  // 做访问标记
                q.push((node){new_floor, step + 1});  // 把子节点加入队列
            } 
        }
    }
    cout << -1;  // 当 while循环执行结束还未 return, 说明数据不成立
}

int main ()
{
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> k[i];  // 把楼层的按钮记录下来
    bfs();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

• dfs 点击查看算法

由于数据更新, 本题dfs只能拿90分,不过为了学习算法,在此也提供dfs的代码

和 bfs 思路大致相同,只不过换成了深入搜索

具体见代码解析

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 205;
int n, a, b;  // n组电梯按钮数  a开始  b目标
int k[N];  // 按钮
int ans = 0x7fffffff;  // 16进制 32 位 int最大值, 在此表示无穷
bool vis[N];  // 判重

void dfs(int now_floor, int step) {
    if (now_floor == b) ans = min(ans, step);  // 如果达到目的地, 第一次记录当前答案, 之后判断最优解
    else if (step < ans) {  // 一个剪枝, 当step >= ans 时,即使得到结果,也不会更新 ans, 可以节省搜索时间
        vis[now_floor] = true;  // 标记来过
        if (now_floor + k[now_floor] <= n && !vis[now_floor + k[now_floor]])  // 当可到达楼层合法, 向上搜索
            dfs(now_floor + k[now_floor], step + 1);
        if (now_floor - k[now_floor] >= 1 && !vis[now_floor - k[now_floor]])  // 当可到达楼层合法, 向下搜索
            dfs(now_floor - k[now_floor], step + 1);
        vis[now_floor] = false;  // 回溯
    }
}

int main (){ 
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> k[i];  // 把楼层的按钮记录下来
    vis[a] = true;  // 起点标记来过
    dfs(a, 0);  
    if(ans == 0x7fffffff) cout << -1;  // 如果 ans 没有更新值, 仍然为无穷, 则无法到达
    else cout << ans;  // 反之,输出距离
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

• floyd 点击查看算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法

由于相邻电梯之间(电梯上的按钮)只需一步就到,故可看为权为 1 的图, 用floyd来求最段路径即可,

由于0x7fffffff 为 int 的最大值, 无法再进行加法, 不然会溢出导致结果错误, 代码中用 1e9 来表示无穷

具体见代码注释

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 205;
int n, a, b;  // n组电梯按钮数  a开始  b目标
int d[N][N];  // 记录相邻(可以互通)的电梯需要的步数(为 1,或无穷, 1即可以到达, 无穷则不可到达)

int main (){ 
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)  // 初始化 权数组  1e9 表示无穷
        for (int j = 1; j <= n; j++)
            if(i != j) d[i][j] = 1e9;  // 当 i == j 时,自己到自己的权(步数)为 0,在全局变量定义时已经为 0, 不再重复赋值
    
    for (int i = 1; i <= n; i++) {  // 读入每个电梯的按钮, 计算他的相邻电梯是否在大楼里
        int k; cin >> k;
        if(i - k >= 1) d[i][i-k] = 1;  // 如果楼层存在, 则步数为 1
        if(i + k <= n) d[i][i+k] = 1;
    }

    for(int k = 1; k <= n; k ++)
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n; j ++)
                if (i != k && j != k) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  // 典型flody,不多解释

    if (d[a][b] == int(1e9) cout << -1;  // 如果距离是无穷, 则无法到达
    else cout << d[a][b];  // 反之,输出距离
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29