【搜索之BFS】杭电 hdu 1548 A strange lift

 

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1548
    Name  : 1548 A strange lift

    Date  : Sunday，April 1, 2012
    Time Stage : many hours

    Result:
5685230	2012-04-01 18:17:43	Accepted	1548
0MS	244K	1689 B
C++	pyy

Test Data :

Review :
一开始一直MLE，真是莫名奇妙啊，完全不知道原因，在原代码的基础上改来改去不得其法。
后来直接重新写一遍，酸酸地AC了……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std ;

#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value
#define max(x, y)        ((x) > (y) ? (x) : (y))
#define min(x, y)        ((x) < (y) ? (x) : (y))

#define INF        (0x3f3f3f3f)
#define MAXN    (202)
#define MAXM    (100)

#define DB    /##/
#define LL __int64

#define _IN(a)			(0 < (a) && (a) <= n)
#define CHECK(a)		(_IN(a) && -1 == step[(a)])
#define LOAD(a)			do { q.push(a); step[(a)] = step[t] + 1; } while(0)

int		n, a, b;
int		step[MAXN], next[MAXN];

void bfs()
{
	int t, na, nb;
	queue<int>	q;

	q.push(a);
	while (!q.empty())
	{
		t = q.front();
		q.pop();

		if (t == b)
			break;

		na = t + next[t];
		nb = t - next[t];
		if (CHECK(na))
		{
			LOAD(na);
/*
			q.push(na);
			step[na] = step[t] + 1;
*/
		}
		if (CHECK(nb))
		{
			LOAD(nb);
/*
			q.push(nb);
			step[nb] = step[t] + 1;
*/
		}
	}
}

int main()
{
	int i;
	while (scanf("%d", &n), n)
	{
		scanf("%d %d", &a, &b);
		MEM(step, -1);
		step[a] = 0;
		for (i = 1; i <= n; ++i)
			scanf("%d", &next[i]);
		bfs();
		printf ("%d\n", step[b]);
	}
	return 0;
}