洛谷p1135

分析:

提取关键字,至少,所以本题用bfs来解。

每一个电梯都有可以运动的步长,而且只能是这么长,所以我们要到达目的地要尝试在别的楼层转乘电梯,用bfs来暴力破解,达到楼层后立即返回,这个就不会超时。

代码:

#include<stdio.h>
struct point{
	int place;
	int step;
};
int book[500];//标记已经走过的路线 
int n,aim;//n为楼高,aim为目标楼层 
int end=0;//队尾 
struct point queue[100000];//队列 
int move[300];//每层楼的步长,也是我们移动的依据 
int bfs()
{
	int front=0;
	while(front<end)
	{
		if(queue[front].place==aim) return queue[front].step;
		struct point goup,godown;
		goup.place=queue[front].place+move[queue[front].place];
		godown.place=queue[front].place-move[queue[front].place];
		if(goup.place<=n&&!book[goup.place]) {
													book[goup.place]=1;
													goup.step=queue[front].step+1;
													queue[end++]=goup;
													}
		if(godown.place>0&&!book[godown.place]){
													book[godown.place]=1;
													godown.step=queue[front].step+1;
													queue[end++]=godown;
													}
		++front;
	}
	return -1; 
}
main()
{
	struct point start;
	scanf("%d%d%d",&n,&start.place,&aim);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",move+i);
	}
	book[start.place]=1;
	start.step=0;
	queue[end++]=start;
	printf("%d",bfs());
	//printf("\n");
//	for(int i=0;i<end;i++)
//	{
//		printf("place=%d step%d\n",queue[i].place,queue[i].step);
//	}
}

上一篇:K近邻算法04---案例:预测Facebook签到位置


下一篇:ZOJ 4109 Welcome Party 并查集+优先队列+bfs