hdu2717
题目中,n属于[1-100000],不能走出100000,开始的时候一直写可以多走出一半。在这错了两次。
另外,题意是求最少步数,依然是BFS。这个题纯粹是练习。
题意:
给出起点,终点。可以向前一步,向后一步,向前<<1.求最少步数。
分析:
BFS。
代码:
#include<stdio.h>
#include<queue>
#include<string.h>
bool N[100002];//标记是否搜过
int Min,k;
struct info
{
int a;
int c;
};
std::queue<info> Q;
bool operator<(info x,info y)
{
return x.c>y.c;
}
void BFS(info x)
{
info y,z,w;
Q.push(x);
while(!Q.empty())
{
x=Q.front();Q.pop();N[x.a]=1;
if(x.a==k) {Min=x.c;break;}
y.a=2*x.a;y.c=x.c+1;
z.a=x.a+1;z.c=x.c+1;
w.a=x.a-1;w.c=x.c+1;
if(y.a>0&&y.a<=100000&&N[y.a]==0) Q.push(y);
if(z.a>0&&z.a<=100000&&N[z.a]==0) Q.push(z);
if(w.a>0&&w.a<=100000&&N[w.a]==0) Q.push(w);
}
while(!Q.empty())
{
Q.pop();
}
}
int main()
{
int n;
while(~scanf("%d%d",&n,&k))
{
memset(N,0,sizeof(N));
N[n]=1;
Min=k-n;
info x;
x.a=n;x.c=0;
if(n>=k) Min=n-k;
else BFS(x);
printf("%d\n",Min);
}
return 0;
}
hdu1548
依然是BFS。抵达不了的时候,输出-1;
可以用优先队列优化。
#include<stdio.h>
#include<queue>
#include<string.h>
bool N[202];
int num[202];
int e,n;
struct info
{
int a;
int c;
};
std::priority_queue<info> Q;
bool operator<(info x,info y)
{
return x.c>y.c;
}
int BFS(info x)
{
info y,z,w;
Q.push(x);
while(!Q.empty())
{
x=Q.top();Q.pop();N[x.a]=1;
if(x.a==e) { while(!Q.empty()) Q.pop();return x.c;}
y.a=x.a+num[x.a];y.c=x.c+1;
z.a=x.a-num[x.a];z.c=x.c+1;
if(y.a>0&&y.a<=n&&N[y.a]==0) Q.push(y);
if(z.a>0&&z.a<=n&&N[z.a]==0) Q.push(z);
}
return -1;
}
int main()
{
int b,i;
while(scanf("%d",&n)&&n!=0)
{
scanf("%d%d",&b,&e);
memset(N,0,sizeof(N));
for(i=0;i<n;i++)
scanf("%d",&num[i+1]);
info x;
x.a=b;x.c=0;
printf("%d\n",BFS(x));
}
return 0;
}
分享到:
相关推荐
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
【项目资源】: 包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。 ... 【项目质量】: 所有源码都经过严格测试,...
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
1548 --- basic bfs 2. BNU 1440 --- basic dfs 3. POJ 1190 --- dfs + pruning(Strong) 4. UVALive 2243 --- dfs 5. FZU 2196 --- double bfs 6. PKU 1426 --- bfs + pruning 7. BNU 1038 --- dfs transform 8. PKU...
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
HDU2013暑期多校联合训练第一场0723-解题报告和标程
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
HDU1059的代码
2017hdu多校联合训练第一场标程及数据
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。