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

 

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

    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 ("God please help our poor hero.\n");
		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;
}