洛谷 P1135 奇怪的电梯

佚名 6年前 (2019-04-09) 随笔 1473人围观抢沙发百度已收录

奇怪的电梯

题目链接

这个电梯真的好奇怪哦，这种电梯怕不是要急死快要迟到的人qwqwq
这道题LITTLESUN用了bfs，记录每一层楼的同时记录次数。注意在结束是进行标记用于输出到达不了的情况其实也可以在最后直接特判r.floor
AC代码如下

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 10100
using namespace std;
int N,A,B;
int G[MAXN];
int vis[MAXN];
bool book;
struct item
{
    int floor;
    int time;
};
item r;
queue<item>q;
void bfs(item t)
{
    q.push(t);
    while(!q.empty())
    {
        r=q.front();
        vis[r.floor]=1;
        q.pop();
        if(r.floor==B) 
        {
            book=1;
            break;
        }
        int a=r.floor+G[r.floor];
        if(vis[a]==0&&a<=N)
        {
            item t2;
            t2.floor=a;
            t2.time=r.time+1;
            q.push(t2);
        }
        a=r.floor-G[r.floor];
        if(vis[a]==0&&a>=1)
        {
            item t2;
            t2.floor=a;
            t2.time=r.time+1;
            q.push(t2);
        }
    }
    
}
int main()
{
    scanf("%d%d%d",&N,&A,&B);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&G[i]);
    }
    item t;
    t.floor=A;
    t.time=0;
    bfs(t);
    if(book)
    {
        printf("%d",r.time);
    }
    else printf("-1");
    return 0;
}