Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13724 Accepted Submission(s): 5239
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int N,A,B;
int flor[250];
int dir[]={-1,1};//上下方向
struct node{
int x;//楼层
int step_cnt;//步数
};
node now,nextf;
node vs,vd;//起点和终点
int leap;
int vis[250];//标记数组只需一维,即标记刚入队的nextf,下次不用再回到此处,
//因你到了nextf结点后,只会有上下两个选择,即使下次再回到此处
//面对的仍是上下两个选择,而在第一次就可抉择
void in_put()
{
scanf("%d%d",&A,&B);
for(int i=1;i<=N;++i)
scanf("%d",&flor[i]);
vs.x=A;
vd.x=B;
}
void bfs()
{
queue<node>Q;
vs.step_cnt=0;
Q.push(vs);
while(!Q.empty()){
now=Q.front();
Q.pop();
if(now.x==vd.x) {leap=1;return;}
for(int i=0;i<2;++i){
nextf.x=now.x+dir[i]*flor[now.x];
nextf.step_cnt=now.step_cnt+1;
if(nextf.x>=1&&nextf.x<=N&&!vis[nextf.x]) {Q.push(nextf);vis[nextf.x]=1;}//迷之wa,原因在于写出了vis[now.x]=1;
}
}
}
int main()
{
while(scanf("%d",&N)&&N){
leap=0;
memset(vis,0,sizeof(vis));
in_put();
bfs();
if(leap)
printf("%d\n",now.step_cnt);
else printf("-1\n");
}
}
原文:http://www.cnblogs.com/orchidzjl/p/4369841.html