P1135题解

做法

本题使用 BFS 来做是又快又简单的。

实现

BFS 广度优先搜索是使用队列（queue，先进先出）来实现，整个过程也可以看做一个倒立的树形：

1. 把根节点放到队列的末尾。
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾 (不需要排序，因为默认每次增加权重相同)。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历整个树还没有找到，结束程序。

最坏情况 $\Theta(n)$。

代码

#include<bits/stdc++.h>
#define maxn 200+10
using namespace std;
int n,k[maxn],a,b,bb[maxn];
struct node{
	int k,step;
	node(int kk,int st){
		k=kk;step=st;
	}
};
queue<node> q;
inline bool p(int dx){
	return dx<=n&&dx>=1;
}
int bfs(int x,int y){
	int dx;
	if(x==y) return 0;
	q.push(node(x,0));
	bb[x]=true;
	while(!q.empty()){
		node no=q.front();
		q.pop();
		dx=no.k+k[no.k];
		if(p(dx)&&bb[dx]==false){
			bb[dx]=true;
			q.push(node(dx,no.step+1));
			if(dx==y) return no.step+1;
		}
		dx=no.k-k[no.k];
		if(p(dx)&&bb[dx]==false){
			bb[dx]=true;
			q.push(node(dx,no.step+1));
			if(dx==y) return no.step+1;
		}
	}
	return -1;
}
int main(){
	std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>k[i];
	cout<<bfs(a,b)<<endl;
	return 0;
}