洛谷 P1135 奇怪的电梯

题目描述

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

输入格式

共二行。

第一行为

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

输出格式

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

输入输出样例

输入 #1

5 1 5
3 3 1 2 5

输出 #1

3
//苟了50

 1 #include <bits/stdc++.h>
 2 #include <queue>
 3 using namespace std;
 4 
 5 int N,A,B;
 6 int K[205];
 7 struct node{
 8     int floor,step;
 9 };
10 bool vis[205];
11 void bfs(){
12     queue<node> q; 
13     q.push((node){A,0});//根节点入队列
14     vis[A]=1;
15     while(!q.empty()){
16         if(A==B) {cout<<0;return;}//特判
17         node now=q.front();q.pop();//取出队首
18         int floor=now.floor,step=now.step;
19         if(floor==B){
20             cout<<step;return;
21         } 
22         int nextfloor;
23         if(floor+K[floor]>N) {
24             nextfloor=floor-K[floor];
25         }
26         else if(floor-K[floor]<A){
27             nextfloor=floor+K[floor];
28         }
29         nextfloor=nextfloor;    
30         if(nextfloor>=1 && nextfloor<=N && vis[nextfloor]==false){
31             vis[nextfloor]=true;//访问标记
32             q.push((node){nextfloor,step+1});
33         }
34     } 
35     puts("-1");//无解     
36 } 
37 int main(){
38     cin>>N>>A>>B;
39     for(int i=1;i<=N;i++)
40         cin>>K[i];
41     bfs();
42 }

//下载了数据修改之后，苟了80

#include <bits/stdc++.h>
#include <queue>
using namespace std;

int N,A,B;
int K[205];
struct node{
    int floor,step;
};
bool vis[205];
void bfs(){
    queue<node> q; 
    q.push((node){A,0});//根节点入队列
    vis[A]=1;
    while(!q.empty()){
        if(A==B) {cout<<0;return;}//特判
        node now=q.front();q.pop();//取出队首
        int floor=now.floor,step=now.step;
        if(floor==B){
            cout<<step;return;
        } 
        int nextfloor;
        if(floor+K[floor]>N) {
            nextfloor=floor-K[floor];
        }
        else if(floor-K[floor]<A){
            nextfloor=floor+K[floor];
        }else{
            nextfloor=floor+K[floor];
        }
        nextfloor=nextfloor;    
        if(nextfloor>=1 && nextfloor<=N && vis[nextfloor]==false){
            vis[nextfloor]=true;//访问标记
            q.push((node){nextfloor,step+1});
        }
    } 
    puts("-1");//无解     
} 
int main(){
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++)
        cin>>K[i];
    bfs();
}

//看完题解之后，发现前面的做法。。。只能算凑答案，以下使用bfs苟出的100

#include <bits/stdc++.h>
#include <queue>
using namespace std;

int N,A,B;
int K[205];
struct node{
    int floor,step;
};
bool vis[205];
void bfs(){
    queue<node> q; 
    q.push((node){A,0});//根节点入队列
    vis[A]=1;
    while(!q.empty()){
        if(A==B) {cout<<0;return;}//特判
        node now=q.front();q.pop();//取出队首
        int floor=now.floor,step=now.step;
//        cout<<floor<<" "<<K[floor]<<" "<<step<<endl;
        if(floor==B){
            cout<<step;return;
        } 
        int nextfloor;
        if(floor+K[floor]<=N && vis[floor+K[floor]]==false){
            nextfloor=floor+K[floor];
            vis[nextfloor]=true;
            q.push((node){nextfloor,step+1});
        }
        if(floor-K[floor]>=1 && vis[floor-K[floor]]==false){
            nextfloor=floor-K[floor];
            vis[nextfloor]=true;
            q.push((node){nextfloor,step+1});
        }    
    } 
    puts("-1");//无解     
} 
int main(){
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++)
        cin>>K[i];
    bfs();
}

将每一次所有有可能的解全部都push进队列中！！！