# 【搜寻之BFS + 优先队列】杭电 hdu 1026 Ignatius and the Princess I

www.myexceptions.net  网友分享于：2013-08-25  浏览：4次
【搜索之BFS + 优先队列】杭电 hdu 1026 Ignatius and the Princess I

```/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------//

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1026
Name  : 1026 Ignatius and the Princess I

Date  : Monday, April 2, 2012
Time Stage : 3 hours

Result:
5689062	2012-04-02 12:05:54	Accepted	1026
15MS	496K	4200 B
C++	pyy

5688705	2012-04-02 11:02:19	Wrong Answer	1026
15MS	404K	4449 B
C++	pyy

5688696	2012-04-02 11:01:44	Compilation Error
1026
0MS	0K	4493 B
C++	pyy

5688688	2012-04-02 11:00:26	Compilation Error
1026
0MS	0K	4493 B
C++	pyy

5688467	2012-04-02 10:36:55	Wrong Answer	1026
15MS	404K	3747 B
C++	pyy

Test Data :

Review :

//----------------------------------------*/

#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    (102)
#define MAXM    (100)

#define DB    /##/
#define LL __int64

#define SEC(pt)		path[(pt).x][(pt).y].sec
#define PRE(pt)		path[(pt).x][(pt).y].pre
#define MAP(pt)		map[(pt).x][(pt).y]
#define _IN_RANGE(a, s, e)	((s) <= (a) && (a) < (e))
#define _IN_X(a)	(_IN_RANGE(a, 0, n))
#define _IN_Y(b)	(_IN_RANGE(b, 0, m))
#define _IN(pt)		(_IN_X(pt.x) && _IN_Y(pt.y))
#define _IS_NUM(a)	_IN_RANGE(a, '0', '9'+1)
#define _NUM(n)		((n)-'0')
#define PATH(p)		path[p.x][p.y]

int		n, m;

char	map[MAXN][MAXN];

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

struct POINT {
int x, y;
POINT(int i = -1, int j = -1): x(i), y(j) {}
bool operator== (const POINT &pt) {
return pt.x == x && pt.y == y;
}
POINT operator+ (const POINT &pt) {
return POINT(this->x + pt.x, this->y + pt.y);
}
};

struct NODE {
NODE(POINT cu = POINT(), POINT pt = POINT(), int s = INF):
cur(cu), pre(pt), sec(s) {}
POINT pre, cur;
int sec;
bool operator< (const NODE nd) const {
return sec > nd.sec;
}
} path[MAXN][MAXN];

NODE	BEG, END;

void bfs()
{
int i, j, flag;
priority_queue<NODE>	q;

q.push(BEG);
while (!q.empty())
{
NODE nd = q.top();
POINT t = nd.cur;
q.pop();

if (t == END.cur)
break;

DB		printf ("----for -----\n");
for (i = 0; i < 4; ++i)
{
POINT nt = t + POINT(dir[i][0], dir[i][1]);

if (!_IN(nt) || 'X' == MAP(nt))
continue;

DB			flag = 0;
if ('.' == MAP(nt))
{
if (SEC(nt) > SEC(t) + 1)
{
SEC(nt) = SEC(t) + 1;
PRE(nt) = t;
q.push(PATH(nt));
DB					flag = 1;
}
}
else if (_IS_NUM(MAP(nt)))
{
if (SEC(nt) > SEC(t) + 1 + _NUM(MAP(nt)))
{
SEC(nt) = SEC(t) + 1 + _NUM(MAP(nt));
PRE(nt) = t;
q.push(PATH(nt));
DB					flag = 1;
}
}

DB			printf ("t: %d, %d. MAP: %c, NODE: sec: %d, pre(%d,%d)\n",		\
t.x, t.y, MAP(t), SEC(t), PRE(t).x, PRE(t).y);
DB			printf ("nt: %d, %d. MAP: %c .NODE: sec: %d\n",					\
nt.x, nt.y, MAP(nt), SEC(nt));
DB			if (flag) printf ("push: (%d, %d)\n", nt.x, nt.y);
DB			getchar();
}
}
}

void dfs(POINT pt)
{
if (pt == BEG.cur)
{
return ;
}

dfs(PRE(pt));

if (_IS_NUM(MAP(pt)))
{
int cnt = _NUM(MAP(pt));
printf ("%ds:(%d,%d)->(%d,%d)\n", SEC(pt)-cnt, PRE(pt).x, PRE(pt).y,
pt.x, pt.y);

for (int i = 1; i <= cnt; ++i)
{
printf ("%ds:FIGHT AT (%d,%d)\n", i+SEC(pt)-cnt, pt.x, pt.y);
}
}
else {
printf ("%ds:(%d,%d)->(%d,%d)\n", SEC(pt), PRE(pt).x, PRE(pt).y,
pt.x, pt.y);
}
}

void out()
{
POINT T = END.cur;
if (INF == SEC(T))
{
printf ("FINISH\n");
return ;
}

printf ("It takes %d seconds to reach the target position, let me show "
"you the way.\n", SEC(END.cur));
dfs(END.cur);
printf ("FINISH\n");
}

void init()
{
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < m; ++j)
{
path[i][j].cur = POINT(i, j);
path[i][j].pre = POINT(-1, -1);
path[i][j].sec = INF;
}

BEG = NODE(POINT(0, 0), POINT(-1, -1), 0);
END = NODE(POINT(n-1, m-1));
SEC(BEG.cur) = 0;
}

int main()
{
int i, j;
while (scanf("%d %d", &n, &m) != EOF)
{
init();
for (i = 0; i < n; ++i)
{
getchar();
for (j = 0; j < m; ++j)
scanf("%c", &map[i][j]);
}

bfs();
out();
}
return 0;
}
```