【搜索之BFS + 优先队列】杭电 hdu 1242 Rescue

?

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2012 panyanyany All rights reserved.    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1242    Name  : 1242 Rescue    Date  : Wednesday, April 4, 2012    Time Stage : half an hour    Result:57038312012-04-04 16:03:27Accepted124231MS304K2294 BC++pyy57038232012-04-04 16:02:46Wrong Answer124231MS304K2287 BC++pyy57038012012-04-04 15:59:41Wrong Answer124231MS304K2280 BC++pyy57037882012-04-04 15:57:34Wrong Answer124215MS308K2284 BC++pyyTest Data :Review :题目描述是 "r" stands for each of Angel's friend. 一听到就心虚了，万一有几个朋友怎么办？于是应该以’a’为起点，然后任意一个’r’为终点跳出。//----------------------------------------*/#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 DB    /##/#define LL __int64struct NODE {int x, y;int step;bool operator== (const NODE &nd) {return x == nd.x && y == nd.y;}bool operator< (const NODE &nd) const {return step > nd.step;// 优先队列好像是按从大到小排序的……}} ;#define PATH(nd)path[(nd).y][(nd).x]#define MAP(nd)map[(nd).y][(nd).x]#define _RANGE(v, s, e)((s) <= (v) && (v) < (e))#define _IN(nd)(_RANGE(nd.y, 0, n) && _RANGE(nd.x, 0, m))const int dir[4][2] = {0,1, 0,-1, -1,0, 1,0};charmap[MAXN][MAXN];intn, m;NODEbeg, end;void bfs(){int i;priority_queue<NODE>q;// 不用优先队列就AC不了NODEt, nn;end.step = INF;beg.step = 0;q.push(beg);while (!q.empty()){t = q.top();q.pop();for (i = 0; i < 4; ++i){nn = t;nn.y += dir[i][0];nn.x += dir[i][1];if (!_IN(nn) || '#' == MAP(nn))continue;++nn.step;if ('r' == MAP(nn))// 不知道是否有多个朋友，所以要及时跳出{end = nn;return ;}if ('.' != MAP(nn))// 不敢确定守卫的符号是什么，所以只能这样了{++nn.step;// 杀死守卫，时间+1}MAP(nn) = '#';q.push(nn);}}}int main(){int i, j;while (scanf("%d %d", &n, &m) != EOF){for (i = 0; i < n; ++i){getchar();for (j = 0; j < m; ++j){scanf("%c", &map[i][j]);if ('a' == map[i][j]){map[i][j] = '#';beg.y = i;beg.x = j;}}}bfs();if (INF == end.step)printf ("Poor ANGEL has to stay in the prison all his life.\n");elseprintf ("%d\n", end.step);}return 0;}