学步园

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=1026

题意： 给一个 n * m 的矩阵，X 代表墙 . 代表路，若是数字 ，则该点有 怪，需要 打怪。从求 从（0，0 ）点 到  （n-1，m-1）点的用时最小的路，要输出路径。

思路：1：求用时最小路----BFS（广搜）+ 优先队列；

            2：在搜到一个点时对应记录前一个点的坐标！，同时 标记该点（不能再次搜到)；

           3：搜到终点后 从终点 一次向前 找前一个点的坐标，入栈！！

           4：依次出栈，即是 路径！！

   这个题做了一下午呀，第一次遇到要记录路径的广搜，伤脑筋。。。AC代码：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
int map[150][150];
int sx[]={1,-1,0,0},zy[]={0,0,1,-1};
struct hello
{
     friend bool operator< (hello n1, hello n2)
    {
        return n1.step > n2.step;
    }
    int x,y;
    int step;
};
struct sb
{
    int x,y;
    int f;
}ac[150][150];
struct fuck
{
    int x,y;
    int xs,ys;
    int step;
    int stop;
};
void find_path(int n,int m,int step)
{
    int a,b;
    stack<fuck> S;
    while(step&&n>=0&&m>=0)
    {
        //printf("%d  %d--------------- %d %d\n",n,m,ac[n][m].x,ac[n][m].y);
        if(ac[n][m].f==0)
        {
            fuck t1={n,m,ac[n][m].x,ac[n][m].y,step,0};
            step--;
            S.push(t1);
        }
        else
        {
            fuck t1={n,m,ac[n][m].x,ac[n][m].y,step-ac[n][m].f,ac[n][m].f};
            step-=  ac[n][m].f;
            step--;
            S.push(t1);
        }
        a=n;b=m;
        n=ac[a][b].x;
        m=ac[a][b].y;
    }
    while(!S.empty())
    {
        fuck t1;
        t1.x=S.top().x;
        t1.y=S.top().y;
        t1.step=S.top().step;
        t1.stop=S.top().stop;
        t1.xs=S.top().xs;
        t1.ys=S.top().ys;
        printf("%ds:(%d,%d)->(%d,%d)\n",t1.step,t1.xs-1,t1.ys-1,t1.x-1,t1.y-1);
        while(t1.stop--)
        {
            printf("%ds:FIGHT AT (%d,%d)\n",++t1.step,t1.x-1,t1.y-1);
        }
        S.pop();
    }
    printf("FINISH\n");
}
void bfs(int n,int m)
{
    int a,b,x,y,i,j,k,step,loop=0;
    priority_queue<hello> Q;
    hello t1={1,1,0};
    Q.push(t1);
    map[1][1]=0;
    while(!Q.empty())
    {
        x= Q.top().x;
        y= Q.top().y;
        step= Q.top().step;
        Q.pop();
        if(x==n&&y==m)
        {loop=1;break;}
        if(loop==1)
            break;
        for(a=0;a<4;a++)
        {
            i= x+sx[a];
            j= y+zy[a];
            if(map[i][j]!=0)
            {
                //printf("***%d  %d**---------------**%d  %d\n",x,y,i,j);
                if(map[i][j]==20)
                {
                    ac[i][j].x=x;
                    ac[i][j].y=y;
                    ac[i][j].f=0;
                    hello t2={i,j,step+1};
                    Q.push(t2);
                }
                else if(map[i][j]>=1&&map[i][j]<=9)
                {
                    ac[i][j].x=x;
                    ac[i][j].y=y;
                    ac[i][j].f=map[i][j];
                    hello t2={i,j,step+1+map[i][j]};
                    Q.push(t2);
                }
                map[i][j]=0;
            }
        }
    }
    if(loop==0)
        printf("God please help our poor hero.\nFINISH\n");
    else
    {
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",step);
        find_path(n,m,step);
    }
}
int main()
{
    int a,b,n,m;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        memset(map,0,sizeof(map));
        char ch;
        for(a=1;a<=n;a++)
        {
            for(b=1;b<=m;b++)
            {
                scanf("%c",&ch);
                if(ch>='1'&&ch<='9')
                    map[a][b]=ch-'0';
                else if(ch=='.')
                    map[a][b]=20;
            }
            getchar();
        }
        
        if(map[n][m]==0)
            printf("God please help our poor hero.\nFINISH\n");
        else
            bfs(n,m);
    }
}