【HDU-1548】解题报告（BFS）

原始题目

A strange lift

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 65536/32768 K (Java/Others)
  • Total Submission(s): 32759
  • Accepted Submission(s): 11752

Problem Description

There is a strange lift.The lift can stop can at every floor as you want, and there is a number $K_i (0 K_i 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 \(K_i\) 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 \(K_i\) 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 $k_1 = 3, k_2 = 3 , k_3 = 1 , k_4 = 2 , k_5 = 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 \le N,A,B \le 200)\) which describe above,The second line consist \(N\) integers \(k_1,k_2 \cdots k_n\) .

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

Sample Output

3

Recommend

8600

题目大意

有一个电梯，对于每一层\(i\)，只能上升或者下降\(a_i\)（不能低于\(1\)层或高于\(n\)层），现在给定初态层数和末态层数， 问最少需要操作几次才可以达到末态层数。到达不了输出-1。

解题思路

  • 两方向BFS，注意打标记和输出-1的情况即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
//#include <bits/stdc++.h>
//#define mp make_pair
#define np next_permutation
#define pb push_back
#define fi first
#define se second
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxn=1e4+5;
int vis[maxn];
int mp[maxn],n,a,b;
void bfs(){
	int ans=0;
	int flag=0;
	queue<pii>q;
	q.push(make_pair(a,0));
	memset(vis,0,sizeof(vis));
	vis[a]=1;
	while(!q.empty()){
		pii now=q.front();
		q.pop();
		if(now.fi==b){
			cout<<now.second<<endl;
			flag=1;
			break;
		}
		int down=now.fi-mp[now.fi];
		int up=now.fi+mp[now.fi];
//		cout<<"up="<<up<<"  down="<<down<<endl;
		if(down>=1 && !vis[down]){
			vis[down]=1;
			q.push(make_pair(down,now.second+1));
		}
		if(up<=n && !vis[up]){
			vis[up]=1;
			q.push(make_pair(up,now.second+1));
		}
	}
	if(!flag) cout<<-1<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n&&n){
		cin>>a>>b;
		rep(i,1,n+1)
			cin>>mp[i];
		bfs();
	} 
}

收获与反思

  • 简单bfs，注意打对标记即可。