本文主要是介绍HDU 1548 AStrangeLift，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1548
这是一道广搜的题目。刚开始的时候，还在犹豫深搜可不可以，后来注意到“If you can't reach floor B,printf "-1".”，并且，深搜使用递归寻找递归的边界也不好找，所以，就决定使用广搜了。
在写广搜的时候，出现了几个错误：
1.误认为，这个电梯可以“来回”，而实际上，电梯的up和down,是要进行标记的。如果之前走到过这一层，就不需要再走了，因为如果之前如果到达这一层的时候不能到达目标楼层的话，那么，之后再走到这一层也不会到达目标楼层，相当于“剪枝”。并且，可以防止循环这种情况的发生（1到3,3到1,1到3，......）。
2.在中间过程中判断寻找目标楼层，一旦找到则立即返回到主函数， 减少循环次数，提高时间效率。
3.floor数组，数组下标是楼层号，数组元素代表“权”。
4.bfs小结：
void bfs()
{//队头入队;//标记入队元素;while(!Q.empty() || 未到达目标状态){Q.front();Q.pop(); //取队头；if(){//判断队头是否为目标状态;}if( ) //**情况少的时候，可以列举，多的时候（比如三个水杯）,要根据具体情况，将变量改为数组， 或者使用其他方法，用循环来表达；{ //将队头扩展, 若符合条件(其中包括未被标记这一种情况), 则入队//step++;if(){//一旦找到目标状态则返回， 此时为最优解;return;}Q.push();flag = 1;//标记入队元素}}
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#include<queue>
int N, A, B;
typedef struct lift
{int step;int count;//计数;
}Lift;
int floor[205];
int flag[205];
void bfs();
int main(void)
{while(scanf("%d", &N), N != 0){scanf("%d%d", &A, &B);int i;for(i = 1; i <= N; i ++){scanf("%d", &floor[i]);}memset(flag, 0, sizeof(flag));bfs();}return 0;
}
void bfs()
{queue<Lift>Q;Lift head;head.step = A;head.count = 0;Q.push(head);flag[head.step] = 1;while(!Q.empty()){Lift temp;head = Q.front();Q.pop();if(head.step == B){printf("%d\n", head.count);return ;}if(temp.step = head.step + floor[head.step], 1 <= temp.step && temp.step <= N && flag[temp.step] == 0)//up{temp.count = head.count + 1;if(temp.step == B){printf("%d\n", temp.count);return ;}Q.push(temp);flag[temp.step] = 1;}if(temp.step = head.step - floor[head.step], 1 <= temp.step && temp.step <= N && flag[temp.step] == 0)//down{temp.count = head.count + 1;if(temp.step == B){printf("%d\n", temp.count);return ;}Q.push(temp);flag[temp.step] = 1;}}printf("-1\n");
}这篇关于HDU 1548 AStrangeLift的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
