学步园

题意： 输入n*m的迷宫，‘X’为墙，‘.'代表可走，n代表此处有n个怪兽(1<=n<=9)，你必须花n秒才能从该处走过，每移动一格，花费一秒。最后要找到到达终点所用时间最短的一条路，并按要求输出该路。起点为（0,0）终点为（n-1，m-1）。

因为要比较是否为最小用时路径，则用深搜。

#include<iostream>
#include<string.h>
#include<queue>
#define INF 10000;
using namespace std;
typedef struct 
{
    int x,y;
}Point;
char map[110][110];
Point fa[110][110];      //逆向搜索，由终点向起点搜，fa[][]存的是当前位置的前一步所在位置。 
int step[110][110];      //表示的是起点（这里实际指的是终点(n-1,m-1)）到该点的时间。 
queue<Point> q;
Point e;
int d[4][2]={-1,0,0,1,1,0,0,-1};      //四个方向上x、y轴上的变化。 
int flag,n,m;
void bfs()
{
     Point cur,next;
     e.x=n-1; e.y=m-1;
     if(map[n-1][m-1]=='.') step[n-1][m-1]=0;    //终点也可能有怪兽，初始化“起点”所用时间。 
     else if(judge(n-1,m-1))  step[n-1][m-1]=map[n-1][m-1]-'0';
     while(!q.empty())  q.pop();
     q.push(e);                      //将"起点"入队列 
     while (!q.empty())
     {
           cur=q.front() ;  q.pop();

           if(cur.x==0&&cur.y==0)    //如果，找到一条路标记，但因为该条路并不一定为最小用时路，所以，不能退出循环。 
           {
                flag=1;
           }
               for (int i=0;i<4;i++)   
               {
                   next.x=cur.x+d[i][0];   next.y=cur.y+d[i][1];   //下面分情况，若为'.'则step[next.x][next.y]++. 
                   if(map[next.x][next.y]!='X'&&next.x>=0&&next.x<n&&next.y>=0&&next.y<m)
                   {
                        int len;           //若为n，则step[next.x][next.y]相应加n 
                        if(map[next.x][next.y]!='.')   {len=map[next.x][next.y]-'0';}
                        else len=0;           
                        if (step[cur.x][cur.y]+1+len<step[next.x][next.y])
                        {
                            step[next.x][next.y]=step[cur.x][cur.y]+1+len;
                            fa[next.x][next.y].x=cur.x;  fa[next.x][next.y].y=cur.y;
                            q.push(next);          
                        }
                   }
               }
     }
     return ;
}
int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
          for(int i=0;i<n;i++)
          {
                scanf("%s",map[i]);  
                for(int j=0;j<m;j++)  step[i][j]=INF;
          }
          flag=0;
          bfs();
          if(flag==1)
          {
               printf("It takes %d seconds to reach the target position, let me show you the way.\n",step[0][0]);
               int x=0,y=0;
               for(int i=0;i<step[0][0];i++)
               {   
                    
                    if(map[x][y]!='.'&&map[x][y]!='X') 
                    {
                          for(int j=0;j<map[x][y]-'0';j++)
                          {
                                  printf("%ds:FIGHT AT (%d,%d)\n",i+1,x,y); 
                                  i++;
                          }
                    }
                    if(x!=n-1||y!=m-1)
                    printf("%ds:(%d,%d)->(%d,%d)\n",i+1,x,y,fa[x][y].x,fa[x][y].y);
                    int temp=fa[x][y].x;  y=fa[x][y].y;
                    x=temp;  
               }
          }
          else printf("God please help our poor hero.\n");
          printf("FINISH\n");
    }
    return 0;
}