题解 P1135 【奇怪的电梯】

· · 题解

emmmmm 这是一道特别基础的宽搜， 只要开一个数组纪录每一层楼上的数字。 然后从起始层开始遍历，然后判断当前楼层能去的楼层，如果可以去就加入遍历队列。 搜索方向： 1：上楼；2：下楼； 判断条件： 1:有没有遍历过；2：有没有越界；

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

bool p[1000];
int q[40000];
int step[40000];
int k[1000];
int a,b,n,front,rear;

int main()
{
    cin>>n>>a>>b;

    for (int i=1;i<=n;i++)
    {
        cin>>k[i];
    }

    memset(p,true,sizeof(p));

    q[0]=a;step[0]=0;
    front=0;rear=1;
    p[a]=false;
    while (front < rear)
    {
        int x=q[front];
        if (q[rear-1]==b)
        {
            cout<<step[rear-1]<<endl;
            break;
        }

        if (p[x+k[x]]&&x+k[x]>=1&&x+k[x]<=n)
        {
            q[rear]=x+k[x];
            step[rear]=step[front]+1;
            p[x+k[x]]=false;
            rear++;
        }

        if (q[rear-1]==b)
        {
            cout<<step[rear-1]<<endl;
            break;
        }

        if (p[x-k[x]]&&x-k[x]>=1&&x-k[x]<=n) 
        {
            q[rear]=x-k[x];
            step[rear]=step[front]+1;
            p[x-k[x]]=false;
            rear++;
        }

        if (q[rear-1]==b)
        {
            cout<<step[rear-1]<<endl;
            break;
        }   

        front++;
    }

    if (front==rear)
    {
        cout<<"-1"<<endl;
    }
    return 0;
}

这道题目其实还是可以写得更漂亮一些，开一个常量数组int N={-1,1};这样在下面搜索遍历的时候就可以用一个for循环代替两个if语句。大概实现方式如下。

    for (int i=0;i<=1;i++)
    {
        nx=x+N[i]*k[x];
        .......
    }