把最近刷的题都做一下总结。
HDOJ1548题，搜索类，题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1548
题目大意：电梯只能进行“升”和“降”，每层都有自己对应的“电梯数”，当前层数+电梯数就是对应可到达的层数,但是不能到达不存在的层数，如当前的层数为1，电梯数为3，则摁“UP”可到达第（1+3）层，而摁下“DOWN”却不起作用，因为-2层不存在。给出起始层数和需要到达的目标层数，找到从起始到目标需要摁电梯的最少次数并输出。
用BFS实现，代码如下：
#include<iostream>
using namespace std;
int n,a,b,floor[205],move[2]={1,-1},visit[205],cont;
typedef struct
{
int y;
int count;
}Node;
Node node[205];
int check(int y)
{
int flag=1;
if( visit[y]==1)
flag=0;
if(y<1||y>n)
flag=0;
return flag;
}
void bfs(int start)
{
int i,x;
int head=0;
int tail=1;
node[1].y=start;
node[1].count=0;
while(head!=tail)
{
head++;
for(i=0;i<2;i++)
{
x=node[head].y+move[i]*floor[node[head].y];
if(check(x)==1)
{
tail++;
node[tail].y=x;
node[tail].count=node[head].count+1;
visit[x]=1;
if( node[tail].y==b)
{
cout<<node[ tail].count<<endl;
return ;
}
}
}
}
cout<<"-1"<<endl;
}
int main( )
{
int i;
while(cin>>n&&n)
{
memset(visit,0,sizeof(visit));
cin>>a>>b;
for(i=1;i<=n;i++)
cin>>floor[i];
if(a==b)
cout<<"0"<<endl;
else
bfs(a);
}
return 0;
}