【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 108812
  • 排名 - 230

最新评论

阅读排行榜

评论排行榜

 【问题描述】

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?

 

【输入文件】

输入文件共有二行,第一行为三个用空格隔开的正整数,表示N,A,B(1≤N≤200,1≤A,B≤N),第二行为N个用空格隔开的正整数,表示Ki。

【输出文件】

输出文件仅一行,即最少按键次数,若无法到达,则输出-1。

【输入输出样例】

输入:
5 1 5
3 3 1 2 5

输出:
3

【参考程序】://简单的宽度优先搜索

#include<fstream>
using namespace std;
int step[201],lift[201];
int n,a,b;
int main()
{
        ifstream cin(
"lift.in");
        ofstream cout(
"lift.out");
        cin
>>n>>a>>b;
        
for (int i=1;i<=n;i++)
        {
                cin
>>lift[i];
                step[i]
=-1;
        }
        step[a]
=0;
        
int l=1,p=0,j;
        
while (l>0 && step[b]==-1)
        {
           l
=0;
           
for (int i=1;i<=n;i++)
              
if (step[i]==p)
              {
                  j
=i+lift[i];//两个方向一上一下
                  if (j<=&& step[j]==-1)
                  {
                      step[j]
=p+1;
                      l
=1;
                   }
                   j
=i-lift[i];
                   
if (j>0 && step[j]==-1)
                   {
                       step[j]
=p+1;
                       l
=1;
                   }
             }
             p
++;
        }
        cout
<<step[b]<<endl;
        
return 0;
}
posted on 2009-04-20 11:19 开拓者 阅读(1098) 评论(1)  编辑 收藏 引用 所属分类: 动态规划&背包

Feedback

# re: 【奇怪的电梯(Lift)】[未登录] 2015-04-02 16:54
#include<iostream>
using namespace std;
long long Up[1000000]={0},Down[1000000]={0},small=9999999;
void dfs(long long root,long long deep,long long end)
{
if(root==end)
{
if(deep<small)small=deep;
return;
}
if(Up[root-1]!=0&&Up[root-1]!=root)dfs(Up[root-1],deep+1,end);
if(Down[root-1]!=0&&Down[root-1]!=root)dfs(Down[root-1],deep+1,end);
return;
}
int main(void)
{
long long n,a,b,i,temp;
cin>>n>>a>>b;
if(a<1||b>n)
{
cout<<"-1"<<endl;
return 0;
}
for(i=1;i<=1000000;i++)
{
Down[i-1]=0;Up[i-1]=0;
}
for(i=1;i<=n;i++)
{
cin>>temp;
if((i-temp)>=1) Down[i-1]=i-temp;
if((i+temp)<=n) Up[i-1]=i+temp;
}
dfs(a,0,b);
if(small!=9999999)cout<<small<<endl;
else cout<<"-1"<<endl;
return 0;
}
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理