372

# 题目

## Description

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"?

## Input

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.

## Output

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".

## Sample Input

5 1 5 3 3 1 2 5 0

3

BFS题目

# 代码

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！

*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 205;
int k[maxn];
int N;

int BFS(int s,int v) {
if(s == v)
return 0;

queue<int> Q;
bool visited[maxn];
memset(visited,false,sizeof(visited));
int dis[maxn];
memset(dis,0,sizeof(dis));

Q.push(s);
visited[s] = true;
while(!Q.empty()) {
int th = Q.front();
Q.pop();

//达到终点
if(th == v)
break;

//拓展节点
int next;
for(int i = -1;i == -1 || i == 1;i += 2) {
next = th + i * k[th];
if(next > N || next <= 0)
continue;
if(!visited[next]) {
Q.push(next);
visited[next] = true;
dis[next] = dis[th] + 1;
}
}

}

if(dis[v])
return dis[v];
else
return -1;
}

bool Do() {
int s,v;
if(scanf("%d%d%d",&N,&s,&v),N == 0)
return false;
REP(N)
scanf("%d",&k[o + 1]);
printf("%d\n",BFS(s,v));
return true;
}

int main() {
while(Do());
return 0;
}

• 点击查看/关闭被识别为广告的评论