这道题搞了很久啊。搜索非常好的一道题。昨天想了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);
}
}
}