P1135 奇怪的电梯

 题目大意：

求出A楼到B楼至少要按几次按钮。

思路：

求出最短的次数，我想到的是用广搜来解。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,a,b,bj=1;//n,a,b具体看题目，bj表示是否能到达B楼 
long long k[101000],book[101000];//k数组为每层楼的数，book数组用来标记是否访问过 
struct Node{
    int cs;//层数 
    int ans;//答案 
}q[101000];//数组模拟队列 
void bfs(){
    int head=0,tail=1,dq;//头，尾，dq表示当前楼层 
    q[1].cs=a;//当前层数 
    q[1].ans=1;//当前的答案 
    book[a]=1;//标记 
    while(head<tail){
        head++;//头++，相当于入栈 
        dq=q[head].cs+k[q[head].cs];//如果上楼，计算当前的层数 
        if(dq>=1&&dq<=n&&book[dq]==0){//判断是否越界，是否访问过 
            tail++;//尾++，出栈 
            q[tail].ans=q[head].ans+1;//更新答案 
            q[tail].cs=dq;//更新当前层数 
            book[q[tail].cs]=1;//标记为访问过 
        }
        if(dq==b){//如果到B楼了 
            bj=2;//标记为可以到达 
            printf("%lld
",q[head].ans);//输出答案 
            return;//退出 
        }
        dq=q[head].cs-k[q[head].cs];//如果下楼，计算当前的层数
        if(dq>=1&&dq<=n&&book[dq]==0){//判断是否越界，是否访问过
            tail++;//尾++，出栈
            q[tail].ans=q[head].ans+1;//更新答案
            q[tail].cs=dq;//更新当前层数
            book[q[tail].cs]=1;//标记为访问过
        }
        if(dq==b){//如果到B楼了
            bj=2;//标记为可以到达
            printf("%lld
",q[head].ans);//输出答案 
            return;//退出
        }
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&a,&b);//输入 
    for(int i=1;i<=n;i++){
        scanf("%lld",&k[i]);//输入 
    }
    bfs();//搜索 
    if(bj==1){//如果不能到达B楼 
        printf("-1
");
    }
    return 0;
}

 你以为这样就结束了？

 其实这个代码只能得90分。

 所以这里提醒大家一定要特判，如果a和b相等，输出0，结束程序(因为我自己就栽倒在了这里)

    if(a==b){//特判A楼是否和B楼在同一层！！！
        printf("0
");
        return 0; 
    }

完整代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,a,b,bj=1;
long long k[101000],book[101000];
struct Node{
    int cs;
    int ans;
}q[101000];
void bfs(){
    int head=0,tail=1,dq;
    q[1].cs=a;
    q[1].ans=0;
    book[a]=1;
    while(head<tail){
        head++;
        dq=q[head].cs+k[q[head].cs];
        if(dq>=1&&dq<=n&&book[dq]==0){
            tail++;
            q[tail].ans=q[head].ans+1;
            q[tail].cs=dq;
            book[q[tail].cs]=1;
        }
        if(dq==b){
            bj=2;
            printf("%lld
",q[head].ans);
            return;       
　　　　　}
        dq=q[head].cs-k[q[head].cs];
        if(dq>=1&&dq<=n&&book[dq]==0){
            tail++;
            q[tail].ans=q[head].ans+1;
            q[tail].cs=dq;
            book[q[tail].cs]=1;
        }
        if(dq==b){
            bj=2;
            printf("%lld
",q[head].ans);
            return;
        }
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=1;i<=n;i++){
        scanf("%lld",&k[i]);
    }
    if(a==b){
        printf("0
");
        return 0; 
    }
    bfs();
    if(bj==1){
        printf("-1
");
    }
    return 0;
}