【HDOJ】1026 Ignatius and the Princess I

这道题搞了很久啊。搜索非常好的一道题。昨天想了2小时，以为是深搜，但后来发现深搜怎么也没法输出正确路径。今天拿宽搜试了一下，问题就是普通的队列宽搜没法得到当前时间最小值。看了一下讨论区，发现优先级队列。好久不用了，都忘记了。各种忘记，优先级队列排序都忘掉了。搞了好半天。最后还需要注意的是格式化输出，采用栈格式输出。需要保存每个节点的移动方向。并且注意若终点是怪兽，还是需要"Fight"。这道题目感觉不是一道水题，还挺不错。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <stack>

 using namespace std;

 #define MAXNUM 105

 #define isDigit(ch) ch>='0' && ch<='9'

 typedef struct node_st{

     int x, y, time;

     node_st() {

     }

     node_st(int a, int b, int t) {

         x = a; y = b; time = t;

     }

     friend bool operator < (node_st p, node_st q) {

         return p.time > q.time;

     }

 } node_st;

 priority_queue<node_st> que;

 typedef struct subnode {

     int x, y;

     subnode() {

     }

     subnode (int a, int b) {

         x = a; y = b;

     }

 } subnode;

 stack<subnode> path;

 char map[MAXNUM][MAXNUM];

 bool visit[MAXNUM][MAXNUM];

 int pos[MAXNUM][MAXNUM];

 int direct[][]={{,-}, {-,}, {,}, {,}};

 int n, m;

 void output();

 bool check(int x, int y) {

     if (x>= && x<n && y>= && y<m) {

         if (visit[x][y]==false && map[x][y]!='X')

             return true;

         else

             return false;

     } else

         return false;

 }

 void bfs() {

     node_st cur, next;

     int newx, newy, newt;

     que.push(node_st(,,));

     visit[][] = true;

     while ( !que.empty() ) {

         cur = que.top();

         que.pop();

         // printf("cur node: x=%d,y=%d,cur.time=%d\n",cur.x, cur.y, cur.time);

         if (cur.x==n- && cur.y==m-) {

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

             output();

             printf("FINISH\n");

             return ;

         }

         for (int i=; i<; ++i) {

             newx = cur.x + direct[i][];

             newy = cur.y + direct[i][];

             newt = cur.time + ;

             if ( check(newx, newy) ) {

                 next = node_st(newx, newy, newt);

                 if ( isDigit(map[newx][newy]) )

                     next.time += map[newx][newy] - '';

                 // printf("after check, ch=%c, time=%d\n", map[newx][newy], next.time);

                 pos[newx][newy] = i;

                 visit[newx][newy] = true;

                 que.push(next);

             }

         }

     }

     printf("God please help our poor hero.\n");

     printf("FINISH\n");

 }

 int main() {

     int i;

     while (scanf("%d %d", &n, &m) != EOF) {

         getchar();

         for (i=; i<n; ++i) {

             gets(map[i]);

         }

         memset(visit, false, sizeof(visit));

         memset(pos, , sizeof(pos));

         while (!que.empty())

             que.pop();

         while (!path.empty())

             path.pop();

         bfs();

     }

     return ;

 }

 void output() {

     subnode cur, next;

     int x, y, i, time = ;

     x = n-; y =m-;

     while (x||y) {

         path.push(subnode(x, y));

         i = pos[x][y];

         x -= direct[i][];

         y -= direct[i][];

     }

     // Don;t forget to push (0, 0)

     path.push(subnode(, ));

     cur = path.top();

     path.pop();

     while (!path.empty()) {

         next = path.top();

         x = cur.x;

         y = cur.y;

         if (map[x][y] != '.') {

             i = map[x][y] - '';

             while (i--) {

                 printf("%ds:FIGHT AT (%d,%d)\n", ++time, x, y);

             }

         }

         time++;

         printf("%ds:(%d,%d)->(%d,%d)\n", time, cur.x, cur.y, next.x, next.y);

         cur = path.top();

         path.pop();

     }

     // if final-point has a monster, then ight

     x = next.x;

     y = next.y;

     if (map[x][y] != '.') {

         i = map[x][y] - '';

         while (i--) {

             printf("%ds:FIGHT AT (%d,%d)\n", ++time, x, y);

         }

     }

 }

巴特西

【HDOJ】1026 Ignatius and the Princess I

最新文章

热门文章