这个题我见过!!!

我之前在石油大学的网站上做练习赛,提高了很多,这个题是我第一次在比赛里见到深搜。

当时蒙蔽的一批,现在发现好简单……

这个题和普通的深搜没什么区别,甚至可以说简单了,因为这个是1维的,别的是二维的(见到老熟人,我快高兴疯了)。

我们先来个代码吧,解释什么的写进注释里了:

#include<iostream>
#include<cstdio>
using namespace std;
long long a,b,n;
long long k[300];
long long t,w,bj2=0;
long long sz[1000],bs[1000],bj[300];//不想用queue,就用数组了
void bfs()
{
while(w<=t)
{
if(sz[w]==b)//到地方了,输出一下用了多少步
{
bj2=1;//是可以到达目的地的
cout<<bs[w]<<endl;
return;
}
if(sz[w]+k[sz[w]]<=n&&bj[sz[w]+k[sz[w]]]==0)//向上移动,并且到达的楼层没来过,而且不会飞出去。
{
t++;
sz[t]=sz[w]+k[sz[w]];//加一个新楼层
bs[t]=bs[w]+1;//来这层楼用了几步
bj[sz[w]+k[sz[w]]]=1;//现在来过了
}
if(sz[w]-k[sz[w]]>=1&&bj[sz[w]-k[sz[w]]]==0)//向下移动,并且到达的楼层没来过,而且不会进入地下室
{
t++;
sz[t]=sz[w]-k[sz[w]];//加进来一个新楼层
bs[t]=bs[w]+1;//来这层楼用了几步
bj[sz[w]-k[sz[w]]]=1;//现在来过了
}
w++;
}
}
int main()
{
scanf("%lld%lld%lld",&n,&a,&b);
sz[t]=a;//初始在第a层
bs[t]=0;//不需要移动
bj[a]=1;//第a层来过了
for(int i=1;i<=n;i++)
{
scanf("%lld",&k[i]);//输入
}
bfs();//搜索
if(bj2==0)//如果到达不了目的地,输出-1;
{
cout<<-1<<endl;
}
return 0;
}

是不是简单的不能再简单了,真是个良心题。

04-30 23:03