#include <iostream>#include <cstring>#include <queue>#include <stack>using namespace std;int ans, n, m;const int size = 110;char maze[size][size];bool vis[size][size];int arr[10010];int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };struct data{    int x, y;    int step;    bool operator<(const data& p)const    {        return step>p.step;    }}st;void bfs(){    data now, next;    int xx, yy;    priority_queue<data> q;    while (!q.empty())        q.pop();    st.x = st.y = st.step = 0;    q.push(st);    vis[0][0] = true;    while (!q.empty())    {        now = q.top();        q.pop();        if (now.x == n - 1 && now.y == m - 1)        {            ans = now.step;            return;        }        for (int i = 0; i < 4; i++)        {            xx = now.x + dir[i][0];            yy = now.y + dir[i][1];            if (xx >= 0 && xx < n && yy >= 0 && yy < m && maze[xx][yy] != ‘X‘ && !vis[xx][yy])            {                vis[xx][yy] = true;                next.x = xx;                next.y = yy;                arr[xx*m + yy] = now.x*m + now.y;                if (maze[xx][yy] == ‘.‘)                    next.step = now.step + 1;                else                    next.step = now.step + (maze[xx][yy] - ‘0‘) + 1;                q.push(next);            }        }    }    return;}int main(){    cin.sync_with_stdio(false);    stack<int>s;    int num1, x1, y1, num2, x2, y2;    int k, flag;    while (cin >> n >> m)    {        flag = 0;        while (!s.empty())            s.pop();        memset(vis, false, sizeof(vis));        memset(arr, -1, sizeof(arr));        ans = 0;        k = 1;        for (int i = 0; i < n; i++)        {            for (int j = 0; j < m; j++)            {                cin >> maze[i][j];            }        }        bfs();        if (ans)        {            cout << "It takes " << ans << " seconds to reach the target position, let me show you the way." << endl;            for (int i = n*m - 1; i != 0; i = arr[i])            {                s.push(i);            }            int prex = 0, prey = 0;            while( !s.empty() )             {                num1 = s.top();                s.pop();                x1 = num1 / m;                y1 = num1 % m;                cout << k++ << "s:(" << prex << "," << prey << ")->(" << x1 << "," << y1 << ")" << endl;                if (maze[x1][y1] != ‘.‘)                 {                    for (int i = 0; i < maze[x1][y1] - ‘0‘; i++)                     {                        cout << k++ << "s:FIGHT AT (" << x1 << "," << y1 << ")" << endl;                    }                }                prex = x1;                prey = y1;            }        }        else        {            cout << "God please help our poor hero." << endl;        }        cout << "FINISH" << endl;    }    return 0;}

  1 #include <iostream>  2 #include <cstring>  3 #include <queue>  4 #include <stack>  5 using namespace std;  6   7 int ans , n , m;  8 const int size = 110;  9 char maze[size][size]; 10 bool vis[size][size]; 11 int arr[10010]; 12 int dir[4][2] = {1,0,-1,0,0,1,0,-1}; 13  14 struct data 15 { 16     int x , y; 17     int step; 18     bool operator<(const data& p )const 19     { 20         return step>p.step; 21     } 22 }st; 23  24 void bfs( ) 25 { 26     data now , next; 27     int xx , yy; 28     priority_queue<data> q; 29     while( !q.empty() ) 30         q.pop(); 31     st.x = st.y = st.step = 0; 32     q.push( st ); 33     vis[0][0] = true; 34     while( !q.empty() ) 35     { 36         now = q.top(); 37         q.pop(); 38         if( now.x == n-1 && now.y == m-1 ) 39         { 40             ans = now.step; 41             return; 42         } 43         for( int i = 0 ; i<4 ; i++ ) 44         { 45             xx = now.x + dir[i][0]; 46             yy = now.y + dir[i][1]; 47             if( xx>=0 && xx<n && yy>=0 && yy<m && maze[xx][yy]!=‘X‘ && !vis[xx][yy] ) 48             { 49                 vis[xx][yy] = true; 50                 next.x = xx; 51                 next.y = yy; 52                 arr[xx*m+yy] = now.x*m+now.y; 53                 if( maze[xx][yy] == ‘.‘ ) 54                     next.step = now.step + 1; 55                 else 56                     next.step = now.step + (maze[xx][yy] -‘0‘)+1; 57                 q.push(next); 58             } 59         } 60     } 61     return; 62 } 63  64 int main() 65 { 66     stack<int>s; 67     int num1 , x1 , y1 , num2 , x2 , y2; 68     int k , flag; 69     while( cin >> n >> m ) 70     { 71         flag = 0; 72         while( !s.empty() ) 73             s.pop(); 74         memset( vis , false , sizeof(vis) ); 75         memset( arr , -1 , sizeof(arr) ); 76         ans = 0; 77         k = 1; 78         for( int i = 0 ; i<n ; i++ ) 79         { 80             for( int j = 0 ; j<m ; j++ ) 81             { 82                 cin >> maze[i][j]; 83             } 84         } 85         bfs( ); 86         if( ans ) 87         { 88             cout << "It takes " << ans << " seconds to reach the target position, let me show you the way." << endl; 89             for( int i = n*m-1 ; i!=-1 ; i = arr[i] ) 90             { 91                 s.push( i ); 92             } 93             /* 94             while(!s.empty()) 95             { 96                 cout << s.top() <<endl; 97                 s.pop(); 98             } 99             */100             while( k<ans )101             {102                 num1 = s.top();103                 x1 = num1/m;104                 y1 = num1%m;105                 s.pop();106                 if( maze[x1][y1] ==‘.‘ )107                 {108                     if( !flag )109                     {110                         num2 = s.top();111                         x2 = num2/m;112                         y2 = num2%m;113                         cout<<k<<"s: ("<<x1<<","<<y1<<")->("<<x2<<","<<y2<<")"<<endl;114                     }115                     else116                     {117                         x2 = flag/m;118                         y2 = flag%m;119                         cout<<k<<"s: ("<<x2<<","<<y2<<")->("<<x1<<","<<y1<<")"<<endl;120                         flag = 0;121                     }122                     k++;123                 }124                 else125                 {126                     for( int j = 0 ; j<(maze[x1][y1]-‘0‘) ; j++ )127                     {128                         cout<<k+j<<"s:FIGHT AT ("<<x1<<","<<y1<<")"<<endl;129                     }130                     k+=( maze[x1][y1]-‘0‘ );131                     flag = num1;132                 }133             }134         }135         else136         {137             cout << "God please help our poor hero." << endl;138         }139         cout << "FINISH" << endl;140     }141     return 0;142 }