题意:给出一个电梯,给出它的层数f,给出起点s,终点g,以及在每一层能够上或者下w[i]层,问至少需要按多少次按钮到达终点。

和POJ catch that cow一样,直接用了那一题的代码,发现一直wa,

后来才发现,POJ catch that cow是单组输入的,所以每次调用的时候不用清空队列,而这一题一次输入有多组数据---

用这个清空队列

while(!q.empty()) q.pop();

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 100005
using namespace std;
queue<int> q;
int visit[maxn],step[maxn],n,k,w[maxn],flag,t,sum;
void bfs()
{
int head,next,i;
while(!q.empty()) q.pop(); //注意调用前一定要清空
q.push(n);
visit[n]=1;
step[n]=0;
while(!q.empty())
{
head=q.front(); q.pop();//取出 并弹出队首
for(i=1;i<=2;i++)
{
if(i==1) next=head-w[head];
else next=head+w[head];
if(next>t||next<1) continue;//越界 if(!visit[next])//判重
{
q.push(next);
visit[next]=1;
step[next]=step[head]+1;
if(next==k) //找到终点
{
flag=1;
sum=step[next];
return;
}
}
}
}
return;
}
int main()
{
int i;
while(scanf("%d",&t)!=EOF&&t)
{
memset(visit,0,sizeof(visit));
// memset(step,0,sizeof(step));//不用清空step数组 scanf("%d %d",&n,&k);
for(i=1;i<=t;i++)
scanf("%d",&w[i]);
if(n==k)
{
printf("0\n");
continue;
}
flag=0;
bfs();
if(flag) printf("%d\n",sum);
else printf("-1\n");
}
}

  

最新文章

  1. Android 手机蓝牙接收文件夹
  2. C#的变迁史 - C# 5.0 之其他增强篇
  3. 回传数据startActivityForResult()
  4. 搭建三层架构(ASP.NET MVC+EF)
  5. paip.提升性能----jvm参数调整.txt
  6. C# Winform打包部署时添加注册表信息实现开机启动
  7. 在服务器上log4net没写日志
  8. sublime text 2 配置文件
  9. Backward Digit Sums(暴力)
  10. Deflater与Inflater的压缩与解压缩
  11. nefu 1029 字符串
  12. java后端学习流程
  13. Java WebService学习资料
  14. Python 的编码格式
  15. 马拉车算法——poj3974
  16. vue.js实战——$event
  17. iOS 图片剪切和压缩的几个方法
  18. [Algorithm] A nonrecursive algorithm for enumerating all permutations of the numbers {1,2,...,n}
  19. 前端-CSS-7-标准文档流&amp;行内元素和块级元素转换
  20. Hive是读时模式

热门文章

  1. (转载) Android Studio你不知道的调试技巧
  2. 如何巧妙使用ZBrush中的Image Plane插件
  3. vector的resize与reserve的区别
  4. SQLserver 导入超大CSV(100G以上)方法
  5. ECharts树图节点过多时取消缩放,调整容器高度自适应内容变化
  6. HDU 5762 Teacher Bo ( 暴力 )
  7. SA 学习笔记
  8. js应用中的小细节-时间戳的转换和input输入框有效数字
  9. mysql5.7官网直译SQL语句优化--select语句优化
  10. ZOJ 2836