【搜索之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:56890622012-04-02 12:05:54Accepted102615MS496K4200 BC++pyy56887052012-04-02 11:02:19Wrong Answer102615MS404K4449 BC++pyy56886962012-04-02 11:01:44Compilation Error10260MS0K4493 BC++pyy56886882012-04-02 11:00:26Compilation Error10260MS0K4493 BC++pyy56884672012-04-02 10:36:55Wrong Answer102615MS404K3747 BC++pyyTest 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]intn, m;charmap[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];NODEBEG, 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;DBprintf ("----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;DBflag = 0;if ('.' == MAP(nt)){if (SEC(nt) > SEC(t) + 1){SEC(nt) = SEC(t) + 1;PRE(nt) = t;q.push(PATH(nt));DBflag = 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));DBflag = 1;}}DBprintf ("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);DBprintf ("nt: %d, %d. MAP: %c .NODE: sec: %d\n",\nt.x, nt.y, MAP(nt), SEC(nt));DBif (flag) printf ("push: (%d, %d)\n", nt.x, nt.y);DBgetchar();}}}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;}?