HDU 1026 Ignatius and the Princess I

這個題目一開始沒想到用優先隊列，或許說沒學過優先隊列，結果卡死了。然後看了別人的題解，原來如此，基本方法就是BFS。

優先隊列的基本用法：http://blog.csdn.net/baochunzhi/article/details/7664422，講解還是比較詳細。

這題還有一個注意點就是如何輸出，這裡就要注意前後的關系，我是用next數組來表示前後兩點的相對關系，具體可以見代碼。輸出的時候用到遞歸，從後往前輸。

#include
#include
#include
#include
#include
#include
using namespace std;
struct node
{
    int x,y;
    int time;
    friend bool operator<(node n1,node n2)
    {
        return n2.time=0&&x=0&&y que;
    node cur,_next;
    cur.x=0,cur.y=0,cur.time=0;
    que.push(cur);
    visited[0][0]=true;
    while(!que.empty())
    {
        cur=que.top();
        que.pop();
        if(cur.x==n-1&&cur.y==m-1)
            return cur.time;
        for(int i=0;i<4;i++)
        {
            int x=cur.x+dx[i];
            int y=cur.y+dy[i];
            if(judge(x,y)&&visited[x][y]==false&&map[x][y]!=-1)
            {
                _next.x=x,_next.y=y;
                _next.time=cur.time+1+map[x][y];//這裡要注意加上1，除了打怪獸消耗的時間，還有加上移動的1秒。
                next[x][y]=i+1;//這裡就表示了兩者之間的相對關系，也就是x,y的關系。
                visited[x][y]=true;
                que.push(_next);
            }
        }
    }
    return -1;
}
void print(int x,int y)
{
    if(next[x][y]==0)
        return;
    int pre_x=x-dx[next[x][y]-1];//這裡就展現了如何尋找前面一點。
    int pre_y=y-dy[next[x][y]-1];
    print(pre_x,pre_y);
    printf("%ds:(%d,%d)->(%d,%d)\n",t++,pre_x,pre_y,x,y);
    while(map[x][y]--)
        printf("%ds:FIGHT AT (%d,%d)\n",t++,x,y);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(next,0,sizeof(next));
        char s[N];
        for(int i=0;i