HDU 1548 A strange lift【BFS】
2024-08-31 12:28:51
题意:给出一个电梯,给出它的层数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");
}
}
最新文章
- Android 手机蓝牙接收文件夹
- C#的变迁史 - C# 5.0 之其他增强篇
- 回传数据startActivityForResult()
- 搭建三层架构(ASP.NET MVC+EF)
- paip.提升性能----jvm参数调整.txt
- C# Winform打包部署时添加注册表信息实现开机启动
- 在服务器上log4net没写日志
- sublime text 2 配置文件
- Backward Digit Sums(暴力)
- Deflater与Inflater的压缩与解压缩
- nefu 1029 字符串
- java后端学习流程
- Java WebService学习资料
- Python 的编码格式
- 马拉车算法——poj3974
- vue.js实战——$event
- iOS 图片剪切和压缩的几个方法
- [Algorithm] A nonrecursive algorithm for enumerating all permutations of the numbers {1,2,...,n}
- 前端-CSS-7-标准文档流&;行内元素和块级元素转换
- Hive是读时模式