题目描述

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

输入格式
共二行。
第一行为3个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)
第二行为N个用空格隔开的非负整数，表示Ki

输出格式
一行，即最少按键次数,若无法到达，则输出-1−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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
//————————————————————————————法一：BFS+pair————————————————————————————————
#include <iostream>

using namespace std;

const int N = 210;

typedef pair<int, int> PII;

int n, a, b;
PII q[N];//first存当前楼层数，second存按按钮次数 
bool st[N];
int s[N];//存K值

int bfs(){
	int hh = 0, tt = 0;
	q[0] = {a, 0};
	st[a] = true;
	
	while(hh <= tt){
		auto t = q[hh++];
		if(t.first == b) return t.second;
		int x = t.first + s[t.first];
		if(!st[x] && x <= n){
			q[++tt] = {x, t.second + 1};
			st[x] = true;
		} 
		x = t.first - s[t.first];
		if(!st[x] && x >= 1){
			q[++tt] = {x, t.second + 1};
			st[x] = true;
		}
	}
	return -1;
	 
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> a >> b;
	for(int i = 1; i <= n; ++i){
		cin >> s[i];
	}
	
	cout << bfs() << endl;
	
	return 0;
} 
//————————————————————————————法二：BFS不用pair————————————————————————
#include <iostream>

using namespace std;

const int N = 210;

int n, a, b;
int q[N];
int s[N];
bool st[N];
int ans[N];

int bfs(){
	int hh = 0, tt = 0;
	q[0] = a;
	st[a] = true;
	
	while(hh <= tt){
		int t = q[hh++];
		
		if(t == b) return ans[t];
		
		int x = t + s[t];
		if(!st[x] && x <= n){
			st[x] = true;
			q[++tt] = x;
			ans[x] = ans[t] + 1;
		}
		x = t - s[t];
		if(!st[x] && x >= 1){
			st[x] = true;
			q[++tt] = x;
			ans[x] = ans[t] + 1;
		}
	}
	return -1;
}

int main(){
	scanf("%d%d%d", &n, &a, &b);
	
	for(int i = 1; i <= n; ++i) scanf("%d", &s[i]);
	
	cout << bfs() << endl;
	
	return 0;
}
//——————————————————————————————法三：BFS+stl queue+pair——————————————————————————
#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 210;

int n, a, b;
queue<PII> q;
bool st[N];
int s[N];

int bfs(){
	q.push({a, 0});
	st[a] = true;
	
	while(!q.empty()){
		auto t = q.front();
		q.pop();
		
		if(t.first == b) return t.second;
		int x = t.first + s[t.first];
		if(!st[x] && x <= n){
			st[x] = true;
			q.push({x, t.second + 1});
		}
		x = t.first - s[t.first];
		if(!st[x] && x >= 1){
			st[x] = true;
			q.push({x, t.second + 1});
		} 
	}
	return -1;
}

int main(){
	scanf("%d%d%d", &n, &a, &b);
	
	for(int i = 1; i <= n; ++i) scanf("%d", &s[i]);

	printf("%d", bfs());
	
	return 0;
}
//————————————————————————————————————法四：DFS————————————————————————————
#include <iostream>

using namespace std;

const int N = 210;

int n, a, b;
int ans = 0x3f3f3f3f;
int s[N];
bool st[N]; 

void dfs(int now, int num){
	if(now == b) ans = min(ans, num);
	if(num > ans) return;//剪枝
	
	st[now] = true;
	
	int x = now + s[now]; 
	if(x <= n && !st[x]) dfs(x, num + 1);
	x = now - s[now];
	if(x >= 1 && !st[x]) dfs(x, num + 1);
	
	st[now] = false;//回溯 
} 

int main(){
	scanf("%d%d%d", &n, &a, &b);
	
	for(int i = 1; i <= n; ++i){
		scanf("%d", &s[i]);
	}
	
	dfs(a, 0);
	
	if(ans == 0x3f3f3f3f) printf("-1");
	else printf("%d", ans);
	
	return 0;
}