1.Ignatius can only move in four directions(up, down, left,  right), one step per second. A step is defined as follow: if current position is  (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or  (x,y+1).
2.The array is marked with some characters and numbers. We define  them like this:
. : The place where Ignatius can walk on.
X : The place is  a trap, Ignatius should not walk on it.
n : Here is a monster with n  HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the  monster.

Your task is to give out the path which costs minimum seconds  for Ignatius to reach target position. You may assume that the start position  and the target position will never be a trap, and there will never be a monster  at the start position.

5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.

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://acm.hdu.edu.cn/showproblem.php?pid=1026
 
 
 
这道题我用了spfa的搜索算法，用队列的方式来实现map数组的入列出列，通过dir数组进行各个方向的搜索，在搜索时我用了一个记录方向的量t用以控制使移动方向不会向前面的来的方向移动，做了这个优化，以减少计算量。
 
 
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define M 100000
#define N 101
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct Node{
    int x,y;
    int time,ttime;
};
struct Point{
    int x,y,d;
}p1,p2;

Node map[N][N];
int main()
{
    int n,m,i,j,sum,s,k;
    char ch;
    while (cin>>n>>m)
    {
        sum=0;
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
            {
                map[i][j].ttime=M;
                cin>>ch;
                if (ch=='.')
                    map[i][j].time=1;
                else if (ch=='X')
                    map[i][j].time=0;
                else
                    map[i][j].time=ch-'0'+1;
            }
        queue<Point> q;
        p1.x=n-1;
        p1.y=m-1;
        p1.d=-4;
        map[n-1][m-1].ttime=map[n-1][m-1].time;
        q.push(p1);
        while (!q.empty())
        {
            p1=q.front();
            q.pop();
            if (p1.x==0&&p1.y==0)
                continue;
            for (i=0;i<4;++i)
            {
                if (abs(p1.d-i)==2)
                    continue;
                else
                    p2.d=i;
                p2.x=p1.x+dir[i][0];
                p2.y=p1.y+dir[i][1];
                if (p2.x<0||p2.x>n-1||p2.y<0||p2.y>m-1)
                    continue;
                if (!map[p2.x][p2.y].time)
                    continue;
                if (map[p2.x][p2.y].time+map[p1.x][p1.y].ttime<map[p2.x][p2.y].ttime)
                {
                    map[p2.x][p2.y].ttime=map[p2.x][p2.y].time+map[p1.x][p1.y].ttime;
                    map[p2.x][p2.y].x=p1.x;
                    map[p2.x][p2.y].y=p1.y;
                    q.push(p2);
                }
            }
        }
        if (map[0][0].ttime==M)
            cout<< "God please help our poor hero." <<endl;
        else{
            cout<<"It takes "<<--map[0][0].ttime<<" seconds to reach the target position, let me show you the way."<<endl; 
            i=j=0;
            while (i!=n-1||j!=m-1)
            {
                printf("%ds:(%d,%d)->(%d,%d)\n",++sum,i,j,map[i][j].x,map[i][j].y);
                if (map[map[i][j].x][map[i][j].y].time>1)
                    for (k=1;k<map[map[i][j].x][map[i][j].y].time;++k)
                        printf("%ds:FIGHT AT (%d,%d)\n",++sum,map[i][j].x,map[i][j].y);
                s=i;
                i=map[i][j].x;
                j=map[s][j].y;
            }
        }
        cout<<"FINISH"<<endl;
    }
    return 0;
}