P1135 奇怪的电梯

---

 

题目描述

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

输入格式

共二行。

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

第二行为 NN 个用空格隔开的非负整数，表示 Ki​。

输出格式

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

输入输出样例

输入 #1复制

5 1 5
3 3 1 2 5

输出 #1复制

3

说明/提示

对于 100 \%100% 的数据，1 \le N \le 2001≤N≤200，1 \le A, B \le N1≤A,B≤N，0 \le K_i \le N0≤Ki​≤N。

在洛谷，
享受 Coding 的欢乐

关于洛谷 | 帮助中心 | 用户协议 | 联系我们
小黑屋 | 陶片放逐 | 社区规则 | 招贤纳才
Developed by the Luogu Dev Team
2013-2022 , © 洛谷
增值电信业务经营许可证 沪B2-20200477
沪ICP备18008322号 All rights reserved.

两种,一种深搜,一种广搜

深搜

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,a,b;
int s[205],sum=10000000;
bool f[205];
void  dfs(int x,int y) {
    if(x==b)
        sum= min(sum,y);
    if(y>sum)
        return;
    f[x]=1;
    if(x+s[x]<=n&&!f[x+s[x]]) dfs(x+s[x],y+1);
    if(x-s[x]>=1&&!f[x-s[x]]) dfs(x-s[x],y+1);
    f[x]=0;//回溯
 
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for (int i = 1; i <=n ; ++i) {
        scanf("%d",&s[i]);
    }
    f[a]=1;
    dfs(a,0);
    if(sum!=10000000){
        printf("%d",sum);
    }
    else
        printf("-1");
 
    return 0;
}

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n,a,b;
int s[205],sum=10000000;
bool f[205];
int step=0;
void  bfs(int u) {
    if(u==b){printf("0");return;}
    queue<pair<int,int>>q;
    q.push(make_pair(u,0));
    f[u]=1;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        int x=t.first+s[t.first],y=t.first-s[t.first];
        step=t.second+1;
        if(x==b||y==b){
            printf("%d", step);
            return ;
        }
        if(f[x]==0&&x<=n){
            q.push(make_pair(x,step));
            f[x]=1;
        }
 
        if(f[y]==0&&y>=1){
            q.push(make_pair(y,step));
            f[y]=1;
        }
    }
    printf("-1");
    return;
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for (int i = 1; i <=n ; ++i) {
        scanf("%d",&s[i]);
    }
    bfs(a);
    return 0;
}