http://acm.hdu.edu.cn/showproblem.php?pid=1026
#include<iostream>
#include<stdio.h> 
#include<queue>
#include<string>
using namespace std;
const int MAX = 100000000;
typedef struct node
{
    int x,y;
    int time;
}Node;
struct Infor
{
    int last_x,last_y;
    int time;
};
int sum;
int n,m;
Infor path[102][102];
string maps[102];
int a[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int flag ;

void Bfs()
{
    int k;
    int i,j;
    queue<Node> Q;
    Node p,q;
    p.x = n-1;
    p.y = m-1;
    if(maps[p.x][p.y] == '.')
        p.time = 0;
    else
        p.time = maps[p.x][p.y] - '0';
    Q.push(p);
    path[p.x][p.y].time = p.time;
    while(!Q.empty())
    {
        q = Q.front();
        Q.pop();
        if(q.x == 0 && q.y == 0)
        {
            if( path[q.x][q.y].time > q.time )
                path[q.x][q.y].time = q.time;
        }

        for(k = 0;k < 4;k++)
        {
            i = q.x + a[k][0];
            j = q.y + a[k][1];
            p.x = i;
            p.y = j;
            if(i < 0 || i >= n || j < 0 || j >= m)
                continue;
            if(maps[i][j] == 'X')
                continue;

            if(maps[i][j] == '.')
            {
                if(q.time + 1 < path[i][j].time )
                {
                    p.time = path[i][j].time = q.time + 1;
                    path[i][j].last_x = q.x;//保存路径 
                    path[i][j].last_y = q.y;
                    Q.push(p);
                }
            }
            else 
            {
                if(q.time + 1 + maps[i][j] - '0' <  path[i][j].time )
                {
                    p.time = path[i][j].time = q.time + 1 + maps[i][j] - '0';
                    path[i][j].last_x = q.x;//保存路径
                    path[i][j].last_y = q.y;
                    Q.push(p);
                }
            }

        }
    }
}

void Path(int i,int j,int t)//路径输出 
{    
    int p,q,k;
    if(maps[i][j]>='1' && maps[i][j] <='9')
    {
       k = maps[i][j] - '0';            
        while(k--)
             printf("%ds:FIGHT AT (%d,%d)\n",t++,i,j);
    }
    while(!(i == n-1 && j == m-1))
    {
        if(maps[i][j]>='1' && maps[i][j] <='9')
        {
            k = maps[i][j] - '0';            
            while(k--)
                printf("%ds:FIGHT AT (%d,%d)\n",t++,i,j);
            printf("%ds:(%d,%d)->(%d,%d)\n",t++,i,j,path[i][j].last_x,path[i][j].last_y);
        }
        else
        {   
            printf("%ds:(%d,%d)->(%d,%d)\n",t++,i,j,path[i][j].last_x,path[i][j].last_y);
        }
        p = path[i][j].last_x;
        q = path[i][j].last_y;
        i = p;
        j = q;
    }
    if(maps[i][j]>='1' && maps[i][j] <='9')
    {
        k = maps[i][j] - '0';            
        while(k--)
             printf("%ds:FIGHT AT (%d,%d)\n",t++,i,j);
    }
}
int main()
{
    int i,j;
    while(cin>>n>>m)
    {
        if(n == 0 && m == 0)
            break;
        for(i = 0;i < n;i++)
        {
            cin>>maps[i];            
        }
        
        if(maps[0][0] == 'X' || maps[n-1][m-1] == 'X')//不能走 
        {
            cout<<"God please help our poor hero."<<endl;
            cout<<"FINISH"<<endl;
            continue;
        }

        for(i = 0;i < n;i++)
            for(j = 0;j < m;j++)
            {
                path[i][j].last_x = i;
                path[i][j].last_y = j;
                path[i][j].time = MAX;
            }
        Bfs();
        if(path[0][0].time != MAX)
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",path[0][0].time);
            Path(0,0,1);
        }
        else
        {
            cout<<"God please help our poor hero."<<endl;
        }
        cout<<"FINISH"<<endl;
    }
    return 0;
}