洛谷P1135：奇怪的電梯（bfs）

https://www.luogu.org/problemnew/show/P1135

題目描述

呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第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： 複制

5 1 5
3 3 1 2 5
      

輸出樣例#1： 複制

3
      

解題思路：

簡單搜尋題

#include <stdio.h>
#include <string.h>
#include <queue>
#define N 220
using namespace std;
int a[N], book[N];
struct data{
	int s;
	int v;
}t,x;
queue<data>q;
int main()
{
	int n, A, B, i;
	scanf("%d%d%d", &n, &A, &B);
	for(i=1; i<=n; i++)
		scanf("%d", &a[i]);
	memset(book, 0, sizeof(book));
	t.s=A;
	t.v=0;
	q.push(t);
	book[A]=1;
	while(!q.empty())
	{
		t=q.front();
		if(t.s==B)
			break;
		q.pop();
		if(t.s+a[t.s]>0 && !book[t.s+a[t.s]])
		{
			x.s=t.s+a[t.s];
			x.v=t.v+1;
			q.push(x);
			book[x.s]=1;
		}
		if(t.s-a[t.s]>=0 && !book[t.s-a[t.s]])
		{
			x.s=t.s-a[t.s];
			x.v=t.v+1;
			q.push(x);
			book[x.s]=1;
		}
	}
	if(t.s==B)
		printf("%d\n", t.v);
	else
		printf("-1\n");
	return 0;
}