P1135 奇怪的电梯 题解

· · 题解

洛谷题目传送门！

我的个人博客！

前言

本题是一道经典搜索练习题。

前置知识：

解题步骤

首先看数据范围 n \leq 200 很容易想到搜索，上、下楼的过程直接根据题意模拟即可。

这里用 q 代表头指针，p 代表尾指针的下一位，Q 结构体数组用来储存队列元素。一开始 q=1,p=2，如果要入队则 p++，如果要出队则 q++。

完整代码

//bfs广搜 
#include<bits/stdc++.h>
using namespace std;
int a,b,x[500]/*电梯上的数字*/;
bool vis[500];
int q,p; //头、尾指针 
int N;
struct node
{
    int floor,dep;
}Q[1000];
int bfs() //广搜 
{
    if(a==b) return 0; //如果开始层等于结束层,直接返回0步 
    int ans,top,k;
    Q[1]={a,0};
    q=1;p=2;
    while(q<p)
    {
        top=Q[q].floor;ans=Q[q].dep;
        for(int i=-1;i<=1;i+=2)
        {
            k=top+x[top]*i;
            if (k>=1&&k<=N&&!vis[k])
            {
                vis[k]=true;
                if(k==b) return ans+1;  //到达终点,返回答案 
                Q[p]={k,ans+1}; //入队列 
                p++;
            }
        }
        q++;
    }
    return -1;
}
int main()
{
    cin>>N>>a>>b;
    for(int i=1;i<=N;i++) cin>>x[i];
    cout<<bfs();
    return 0;
}