一手题解

#include<bits/stdc++.h>
using namespace std;
int arr[210],v[210];
struct s{
    int a,b;//a用来存数字，b用来计数
};
queue<s> q;
int main(){
    int n,b,a;
    cin>>n>>a>>b;
    s ddd={a,0};
    q.push(ddd);//初始化，要把a入队
    for(int i=1;i<=n;i++) cin>>arr[i];
    while(q.size()){
        s x=q.front();
        int y=arr[x.a];
        if(x.a==b){
            cout<<x.b;
            return 0;
        }//抵达楼层
        v[x.a]=1;
        if(x.a+y<=n && x.a+y>0 && !v[x.a+y]){
            ddd.a=x.a+y;
            ddd.b=x.b+1;
            q.push(ddd);
        }//入队
        if(x.a-y<=n && x.a-y>0 && !v[x.a-y]){
            ddd.a=x.a-y;
            ddd.b=x.b+1;
            q.push(ddd);
        }//入队
        q.pop();//出队
    }
    cout<<"-1";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, x, y;
int k[205];
bool vis[205];
bool f;
struct node
{
	int xx, s;
};

int bfs(int x)
{
	vis[x]=true;
	queue<node> q;
	q.push({x, 0});
	while(!q.empty())
	{
		int cx=q.front().xx;
		int steps=q.front().s;
		q.pop();//用完了扔掉 
		if(cx==y)
		{
			return steps;
			f=true;
		}
		int nx=cx+k[cx];
		int ny=cx-k[cx];
		if(nx>=1&&nx<=n&&!vis[nx])
		{
			q.push({nx, steps+1});
			vis[nx]=true;
		}
		if(ny>=1&&ny<=n&&!vis[ny])
		{
			q.push({ny, steps+1});
			vis[ny]=true;
		}
	}
	if(!f)//无法到达 
	{
		return -1;
	}
}
int main()
{
	cin >> n >> x >> y;
	for(int i = 1; i <= n; i++)
	{
		cin >> k[i];
	}
	int ans=bfs(x);
	cout << ans;
	return 0;
} 

#include<bits/stdc++.h>

using namespace std;
int a[100010];
int x,y;
int n;
bool vis[100010];
struct node{
  //s为当前第几层，cnt为次数
	int s,cnt;
};
int bfs(int x){
	queue<node> q;
	vis[x]=1;
	q.push({x,0});
	while(!q.empty()){
		node ty=q.front();
		q.pop();
		if(ty.s==y) return ty.cnt;
		int ny1=ty.s+a[ty.s];//上升到i+a[i]层
		int ny2=ty.s-a[ty.s];//下降到i-a[i]层
		if(ny1<=n&&vis[ny1]!=1){
			vis[ny1]=1;
			q.push({ny1,ty.cnt+1});
		}
		if(ny2>=0&&vis[ny2]!=1){
			vis[ny2]=1;
			q.push({ny2,ty.cnt+1});
		}
	}
	return -1;
}
int main(){
	cin>>n>>x>>y;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<bfs(x);
	return 0;
} 

#include<iostream>
#include<queue>
#include<vector> 
using namespace std;
const int N=114514;
int n,A,B,t;
struct node
{
	int dt;
	int f;
};
queue<node >q;
int a[N];
int vis[N];
int main()
{
	cin>>n>>A>>B;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	q.push({A,0});
	while(q.size())
	{
		node u=q.front();
		int v=a[u.dt];
		if(u.dt==B)
		{
			cout<<u.f;
			return 0;
		}	
		vis[u.dt]=1;
		if(u.dt+v<=n && !vis[u.dt+v])//上 
		{
			q.push({u.dt+v,u.f+1});
		}
		if(u.dt-v>0 && !vis[u.dt-v])//下 
		{
			q.push({u.dt-v,u.f+1});
		}
		q.pop();
	}
	cout<<-1;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int vis[100005];
int d[114514];
queue<int> q;
int j=0,s=0;
int n,a1,b;
bool f=0;
int h[114514];
void bfs(int s){
	q.push(s);
	//cout<<s.x<<" "<<s.y<<"\n";
	while(!q.empty()){
		int a=q.front();
		q.pop();
		//cout<<a<<"\n";
		if(a==b){
			f=1;
			return ;
		}
		if(a+d[a]<=n){
			if(!vis[a+d[a]]){
			q.push(a+d[a]);
			vis[a+d[a]]=1;
			j++;
			h[a+d[a]]=a/*-d[a]*/;
			//cout<<h[j]<<" "<<j<<endl;
			}
		}
		if(a-d[a]>=1){
			if(!vis[a-d[a]]){
			    q.push(a-d[a]);
			    vis[a-d[a]]=1;
	            j++;
			    h[a-d[a]]=a/*+d[a]*/;
			    //cout<<h[j]<<" "<<j<<endl;
			}
		} 
	} 
}

int main(){
	cin>>n>>a1>>b;
	for(int i=1;i<=n;i++){
		cin>>d[i];
	}
	if(a1==b){
		cout<<0;
		return 0; 
	}
	bfs(a1);
	if(f==0){
		cout<<-1;
		return 0;
	}
	else{
		//cout<<h[1]<<endl;
		//cout<<j;
		for(int i=1;i<=n;i++){
			//cout<<h[i]<<endl;
		}
		while(h[n]!=a1){
			//cout<<h[n]<<" "<<n<<" ";
			n=h[n];
			s++;
		}
		cout<<s+1;
		return 0;
	}
}

题意

本层有一个数 $K_i$，代表如果上要上 $K_i$ 层，下也一样。目标是从 $A$ 到 $B$

思路

结构体存当前层和按了多少下

到了就输出，到不了就走人

PS：$K$ 的索引要从 1 开始，不然会 40 WA

代码

#include <bits/stdc++.h>
using namespace std;
struct lift{
	int x,ceng;
};
int k[205],n,a,b;
bool f[205];
bool bfs(int u){
	queue<lift> q;
	q.push({u,0});
	while (!q.empty()){
		int x = q.front().x,ceng = q.front().ceng;
		if (x == b){
			cout << ceng;
			return 0;	// 不用输出 -1
		}
		f[x] = 1;	// 标记这一层走过了
		if (!f[x + k[x]] && x + k[x] <= n)	q.push({x + k[x],ceng + 1});
		if (!f[x - k[x]] && x - k[x] > 0)	q.push({x - k[x],ceng + 1});
		q.pop();
	}
	return 1;	// 要输出 -1
}
int main(int argc, char **argv){
	cin >> n >> a >> b;
	for (int i = 1;i <= n;i++){	// 层数从 1 开始
		cin >> k[i];
	}
	if(bfs(a))	cout << -1;	// 如果没有答案，输出 -1
	return 0;
}

不想写，点差评吧

#include<iostream>
#include<queue>
#include<vector> 
using namespace std;
const int N=114514;
int n,A,B,t;
struct node
{
	int dt;
	int f;
};
queue<node >q;
int a[N];
int vis[N];
int main()
{
	cin>>n>>A>>B;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	q.push({A,0});
	while(q.size())
	{
		node u=q.front();
		int v=a[u.dt];
		if(u.dt==B)
		{
			cout<<u.f;
			return 0;
		}	
		vis[u.dt]=1;
		if(u.dt+v<=n && !vis[u.dt+v])//上 
		{
			q.push({u.dt+v,u.f+1});
		}
		if(u.dt-v>0 && !vis[u.dt-v])//下 
		{
			q.push({u.dt-v,u.f+1});
		}
		q.pop();
	}
	cout<<-1;
	return 0;
}

题意

在有向图lift中，每个元素都有k值，对于元素i，可到达元素i+k和i-k，但要求$0<i-k,i+k<=n$，若有目标不符合要求，则此无法到达目标。 求元素a到b的最短路距离。

思路

直接bfs。

对于每一个i，找i+k与i-k。如果符合就入队。

同时，如果探查到标记过的节点，就可以判错，因为一定有更短距离可到。

代码

简单的题目题解就是简洁。

#include<iostream>
#include<queue>
using namespace std;
struct f{
	int f;//当前楼层
	int k;
	int t=0;//距a点距离
};
int n,a,b;
f x[300];//这个我本来是喜欢用a的，但是题目占掉了
bool v[300];//vis数组，只用一个字母你们不介意吧~
int main(){
	void bfs();
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>x[i].k;
		x[i].f=i;
	}
	bfs();
	return 0;
}
void bfs(){
	bool check(int);
	queue<f> q;
	q.push(x[a]);
	v[a]=1;
	while(!q.empty()){		
		if(q.front().f==x[b].f){
			cout<<x[b].t;
			return;
		}
		f e=q.front();
		q.pop();
		if(check(e.f+e.k)){
			v[e.f+e.k]=1;
			x[e.f+e.k].t=e.t+1;
			q.push(x[e.f+e.k]);
		}
		if(check(e.f-e.k)){
			v[e.f-e.k]=1;
			x[e.f-e.k].t=e.t+1;
			q.push(x[e.f-e.k]);
		}
	}
	cout<<-1;//没有结果，输出-1
	return;
}
bool check(int f){//
	return (f>0)&&(f<=n)&&!v[f];
}

注意

别爱我，没结果！

还要输出-1哦！