【搜索之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:56852302012-04-01 18:17:43Accepted15480MS244K1689 BC++pyyTest 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)intn, a, b;intstep[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;}