【优先队列广搜+前驱记录】HDU 1026 Ignatius and the Princess I
http://acm.hdu.edu.cn/showproblem.php?pid=1026题意：问从图的左上角到达右下角需要的最短时间，如果格子是数字n（1-9），说明有怪兽，要打死他花费n的时间
Sample Input
http://dl.iteye.com/upload/attachment/540847/127fd4bb-5aab-3153-9f9f-8908897e47d7.png
Sample Output
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
速度还不错：
http://dl.iteye.com/upload/attachment/591354/ae3d709c-6a28-3726-8290-b5c1ae5f3998.png
#include <iostream>#include <queue>using namespace std;#define M 105struct point{int x;int y;int times;friend bool operator < (point a, point b){return a.times > b.times; //重载小于号使得小的先出队列}};struct Pre{int px, py;}pre;int r, c;int x_move = {-1, 0, 1, 0};int y_move = {0, 1, 0, -1};char map;bool vis;void bfs (int x, int y){int i, v;vis = true;point ft, tp;pre.px = -1; //终点标记ft.x = x, ft.y = y, ft.times = 0;if (map != '.')ft.times = map - '0';priority_queue<point> q; //优先队列q.push (ft);while (!q.empty()){ft = q.top();q.pop();if (ft.x == 0 && ft.y == 0){printf ("It takes %d seconds to reach the target position, let me show you the way.\n", ft.times);int key = 1, total = ft.times;x = ft.x, y = ft.y;while (pre.px != -1) //不断寻找前驱直到到达终点{int tx = pre.px;int ty = pre.py;printf ("%ds:(%d,%d)->(%d,%d)\n", key++, x, y, tx, ty);if (map != '.')for (i = 0; i < map - '0'; i++)printf ("%ds:FIGHT AT (%d,%d)\n", key++, tx, ty);x = tx;y = ty;}return ;}for (i = 0; i < 4; i++){tp.x = ft.x + x_move;if (tp.x < 0 || tp.x >= r)continue;tp.y = ft.y + y_move;if (tp.y < 0 || tp.y >= c)continue;if (vis)continue;vis = true;if (map == 'X')continue;if (map == '.')v = 1;else v = map - '0' + 1;tp.times = ft.times + v;/**********记录tp的前驱ft**********/pre.px = ft.x;pre.py = ft.y;/**********记录tp的前驱ft**********/q.push (tp);}}puts ("God please help our poor hero.");}int main(){int i;while (~scanf ("%d%d", &r, &c)){for (i = 0; i < r; i++)scanf ("%s", map);memset (vis, false, sizeof(vis));bfs (r-1, c-1); //倒过来搜索就可以不用栈了puts ("FINISH");}return 0;}
页:
[1]