2013
12-12

# A strange lift

There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can’t go up high than N,and can’t go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you’ll go up to the 4 th floor,and if you press the button "DOWN", the lift can’t do it, because it can’t go down to the -2 th floor,as you know ,the -2 th floor isn’t exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"?

The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,….kn.
A single 0 indicate the end of the input.

For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can’t reach floor B,printf "-1".

5 1 5
3 3 1 2 5
0

3

#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

const int INF = 1 << 30;

int a[222];
bool vis[222];
int n;

struct point
{
int now_floor, step;
};

int Bfs(int star, int end)
{
memset(vis, 0, sizeof(vis));
point q1, q2;
queue <point> q;
q1.now_floor = star - 1;
q1.step = 0;
q.push(q1);
vis[q1.now_floor] = 1;

while (!q.empty())
{
q2 = q.front();
q.pop();

if (q2.now_floor == end - 1)
{
return q2.step;
}

q1.now_floor = q2.now_floor + a[q2.now_floor];
q1.step = q2.step + 1;
if (q1.now_floor < n && q1.now_floor >= 0 && !vis[q1.now_floor])
{

q.push(q1);
vis[q1.now_floor] = 1;
}

q1.now_floor = q2.now_floor - a[q2.now_floor];

if (q1.now_floor >= 0 && q1.now_floor < n && !vis[q1.now_floor])
{
q.push(q1);
vis[q1.now_floor] = 1;
}
}
return -1;

}

int main()
{

int i, j;
int ans;
int star, end;

while (~scanf("%d", &n), n)
{
scanf("%d%d", &star, &end);
for (i = 0; i < n; i++)
{
scanf("%d", a + i);
}

printf("%d\n", Bfs(star, end));

}

return 0;
}

1. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

4. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

5. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

6. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept

7. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。