题意：一个N*M的图，一秒内可上下左右选个方向走一步，一进去，若有数字，就要花数字大小的时间停留在那个格子，输出从起点(0, 0)到终点(N-1, M-1)每一秒的路径。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1026
——>>会选择优先队列来做就基本上没问题了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 100 + 10;
struct node
{int x;int y;int step;int fax;int fay;node(){}node(int xx, int yy): x(xx), y(yy){}bool operator < (const node& e) const{return step > e.step;}void init(int i, int j){x = i;y = j;step = fax = fay = -1;}
}no[maxn][maxn];
char MAP[maxn][maxn];
int N, M, cnt;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};bool bfs()
{priority_queue<node> pq;pq.push(no[0][0]);node temp;while(!pq.empty()){temp = pq.top();pq.pop();for(int i = 0; i < 4; i++){int newx = temp.x + dx[i];int newy = temp.y + dy[i];if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && no[newx][newy].step == -1){no[newx][newy].step = temp.step + 1;if(MAP[newx][newy] != '.') no[newx][newy].step += MAP[newx][newy] - '0';no[newx][newy].fax = temp.x;no[newx][newy].fay = temp.y;pq.push(no[newx][newy]);if(newx == N - 1 && newy == M - 1) return 1;}}}return 0;
}void print(node u)
{if(u.fax == 0 && u.fay == 0){printf("It takes %d seconds to reach the target position, let me show you the way.\n", no[N-1][M-1].step);printf("%ds:(0,0)->(%d,%d)\n", cnt++, u.x, u.y);for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);return;}print(no[u.fax][u.fay]);printf("%ds:(%d,%d)->(%d,%d)\n", cnt++, u.fax, u.fay, u.x, u.y);for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);
}int main()
{int i, j;while(scanf("%d%d", &N, &M) == 2){for(i = 0; i < N; i++)for(j = 0; j < M; j++){cin>>MAP[i][j];no[i][j].init(i, j);}no[0][0].step = 0;cnt = 1;if(bfs()) print(no[N-1][M-1]);else printf("God please help our poor hero.\n");printf("FINISH\n");}return 0;
}