学步园

小记：忘记memset wa了一次。。。

思路：每次有两个方向，上或下。 bfs之，最初碰到的点都是次数最少。这是bfs的特性-最短路。

加个vis标记是否在队列以及是否已经处理过了。并且越界判断 和入队判断

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8

const int MAX_ = 10010;
const int N = 100010;
const int INF = 0x7fffffff;

int a, b, n;
bool vis[MAX_];
int h[MAX_];
int to[MAX_];

int dir[2] = {1,-1};

int bfs(int start)
{
    queue<int >q;
    q.push(start);
    q.push(0);
    vis[start] = 1;
    while(!q.empty()){
        int cur = q.front();q.pop();

        int cnt = q.front(); q.pop();
        if(cur == b)return cnt;


        REP(i, 0, 2){
            int next = dir[i]*to[cur] + cur;
            int tmp = cnt+1;
            if(next > 0 && next <= n){
                if(!vis[next]){
                    vis[next] = 1;
                    q.push(next);
                    q.push(tmp);
                }
            }
        }
    }
    return -1;
}

int main()
{
	int T, m;
	while(scanf("%d", & n), n){
        scanf("%d%d", &a, &b);
        REP(i, 1, n+1){
            scanf("%d", &to[i]);
        }
        mst(vis, 0);
        int tmp = bfs(a);

        printf("%d\n", tmp);
	}
	return 0;
}