题解 P1135 【奇怪的电梯】

典型的BFS题

大体思路

把楼层抽象为一个一维数组，对应K值为行走步数，进行搜索

注：蒟蒻使用数组模拟队列

上代码： （有注释 ）

#include<cstdio>
#include<cstring>
using namespace std;
int head, tail; //头尾指针
struct lift{ 	//存储电梯楼层
    int book;	//标记
    int cnt;	//步数
    int k;	//K值
}l[201];
int a, b, n; 	//如题
int x;   	//临时数据存储
int map[1002];  //队列
int main()
{
    //freopen("data.in", "r", stdin);
    scanf("%d%d%d", &n, &a, &b);//不多说
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &l[i].k);
        l[i].cnt = 0, l[i].book = 0;//初始化
    }
    head = 0, tail = 0;
    l[a].book = 1, l[a].cnt = 0;
    map[head] = a, ++tail;	//初始点特殊处理
    while(head < tail)	//若还能扩展
    {
        x = map[head] + l[map[head]].k; //扩展方式1
        if(x>=1 && x<=n && l[x].book == 0)  //在范围以内且未到过
        {
            map[tail++] = x; //入队
            l[x].book = 1; //打标记
            l[x].cnt = l[map[head]].cnt+1;//步数+1
        }
        if(x == b)//剪枝1
        {
            printf("%d", l[x].cnt);
            return 0;
        }
        x = map[head] - l[map[head]].k;//扩展方式2
        if(x>=1 && x<=n && l[x].book == 0)
        {
            map[tail++] = x;//同上
            l[x].book = 1;
            l[x].cnt = l[map[head]].cnt+1;
        }  
        if(x == b)//剪枝2
        {
            printf("%d", l[x].cnt);
            return 0;
        }
        ++head;//这个楼层扩展完毕，出队
    }
    if(l[b].book == 0)//若无法到达
        printf("-1");
    //fclose(stdin);
    return 0;
}

若有不懂，可以和本蒟蒻一样，阅读《啊哈！算法》